title: 动态规划 Summary
date: 2020-07-06 14:52:26
author: Jason Yuan
tags:
- Algorithm
- Online Judge
categories: Online Judge
(1)动态规划
(1.1)数位 dp 学习
数位dp是一种计数用的dp,一般就是要统计一个区间 [le,ri] 内满足一些条件数的个数。
对应的暴力算法:
for(int i=le;i<=ri;i++) if(right(i)) ans++;
新的枚举:控制上界枚举,从最高位开始往下枚举,例如:ri=213,那么我们从百位开始枚举:百位可能的情况有0,1,2。
例一:HDU 2089 不要62
入门题。就是数位上不能有4也不能有连续的62,没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,所以这个约束没有记忆化的必要,而对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数。
dp[pos][sta]表示当前第pos位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数。
例题 [POJ 3252]
这题的约束就是一个数的二进制中0的数量要不能少于1的数量,通过上一题,这题状态就很简单了,dp[pos][num],到当前数位pos,0的数量减去1的数量不少于num的方案数,一个简单的问题,中间某个pos位上num可能为负数(这不一定是非法的,因为我还没枚举完嘛,只要最终的num>=0才能判合法,中途某个pos就不一定了),这里比较好处理,Hash嘛,最小就-32吧(好像),直接加上32,把32当0用。这题主要是要想讲一下lead的用法,显然我要统计0的数量,前导零是有影响的。至于!lead&&!limit才能dp,都是类似的,自己慢慢体会吧。
(1.2)字符串 dp 复习
- 连个字符串之间的关系往往可以通过 dp 完成。(编辑距离 / 最长公共子序列 / )
(1.3)博弈论 dp 学习
解:记 dp[i] 表示还剩 i+1 … n 时,先手的最大得分。(可能为负数)
状态转化函数:dp[i-1] = max(a[i] + a[i+1] + a[i+2] -dp[i+2], a[i] + a[i+1] - dp[i+1], a[i] - dp[i])
核心:博弈论题目可以考虑动态规划解法:后面的选择与之前怎么到达改状态无关。
状态转移推导:先手交换的思想。
code: (自己写的代码比较凌乱,就不贴了。)
(1.4)经典动态规划
最长公共子序列
// 动态规划求解并输出所有LCS
#include
#include
#include
#include
#include
using namespace std;
string X = "ABCBDAB";
string Y = "BDCABA";
vector> table; // 动态规划表
set setOfLCS; // set保存所有的LCS
int max(int a, int b)
{
return (a>b)? a:b;
}
/**
* 构造表,并返回X和Y的LCS的长度
*/
int lcs(int m, int n)
{
// 表的大小为(m+1)*(n+1)
table = vector>(m+1,vector(n+1));
for(int i=0; i0 && j>0)
{
if (X[i-1] == Y[j-1])
{
lcs_str.push_back(X[i-1]);
--i;
--j;
}
else
{
if (table[i-1][j] > table[i][j-1])
--i;
else if (table[i-1][j] < table[i][j-1])
--j;
else // 相等的情况
{
traceBack(i-1, j, lcs_str, lcs_len);
traceBack(i, j-1, lcs_str, lcs_len);
return;
}
}
}
string str(lcs_str.rbegin(), lcs_str.rend()); // lcs_str逆序
if((int)str.size() == lcs_len) // 判断str的长度是否等于lcs_len
setOfLCS.insert(str);
}
void print()
{
set::iterator beg = setOfLCS.begin();
for( ; beg!=setOfLCS.end(); ++beg)
cout << *beg << endl;
}
int main()
{
int m = X.length();
int n = Y.length();
int length = lcs(m, n);
cout << "The length of LCS is " << length << endl;
string str;
traceBack(m, n, str, length);
print();
getchar();
return 0;
}
最长单调子序列:
直接 dp
class Solution { public: int lengthOfLIS(vector
& nums) { int n=(int)nums.size(); if (n == 0) return 0; vector dp(n, 0); for (int i = 0; i < n; ++i) { dp[i] = 1; for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } } return *max_element(dp.begin(), dp.end()); } }; 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 贪心 + 二分查找
class Solution { public: int lengthOfLIS(vector
& nums) { int len = 1, n = (int)nums.size(); if (n == 0) return 0; vector d(n + 1, 0); d[len] = nums[0]; for (int i = 1; i < n; ++i) { if (nums[i] > d[len]) d[++len] = nums[i]; else{ int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大,此时要更新 d[1],所以这里将 pos 设为 0 while (l <= r) { int mid = (l + r) >> 1; if (d[mid] < nums[i]) { pos = mid; l = mid + 1; } else r = mid - 1; } d[pos + 1] = nums[i]; } } return len; } }; 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
最长回文子序列
class Solution {
public:
int longestPalindromeSubseq(string s1) {
string s2 = s1;
reverse(s2.begin(), s2.end());//s2为s1的逆序列
return longestCommonSubsequence(s1,s2);
}
//最长公共子序列函数
int longestCommonSubsequence(string s1, string s2) {
int l1 = s1.size(),l2=s2.size();
int **dp = new int*[l1+1];
for (int i = 0; i < l1+1; ++i) {
dp[i] = new int[l2+1]();
}
for (int i = 1; i < l1+1; i++) {
for (int j = 1; j < l2+1; j++) {
if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
}
}
return dp[l1][l2];
}
};
作者:njyang-yang-yang
链接:https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dong-tai-gui-hua-zui-jian-dan-si-lu-by-njyang-yang/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。