C++动态规划入门

笔记1 来自算法笔记-胡凡

1.1 斐波那契数列

了解动态规划的递归式写法即记忆化搜索这个名词。利用新开辟的数组记录子问题的解，就达到了记忆化的效果。

从斐波那契数列的递归图中可以看到重叠子问题被计算多次。动态规划真是通过记录重叠子问题的解来减少计算。

在上图中，可以看到重叠子问题。

1.2 数塔问题

• https://leetcode.cn/problems/triangle/

仔细思考，数塔的形状是否和斐波那契递归图很像？

如果令dp[i][j]表示从第i行第j列数字到最底部的最小路径，那么就有dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]

第i层的状态依赖于i+1层，这样就引出来状态转移这个名词。同时容易想到dp数组的初始化边界，最后一层当然是它自己。最后求解的问题答案就是dp[1][1]

还有一种自底向上的思路：分治+递归。此时dp[i][j]不能直接求解答案，而是子问题的解。

注意：这里的分治并不是严格意义上的分治，分治法要求子问题不重叠，我这里只是借助分治的意思。

最后要经历诸如 $min(dp[0],dp[1],...,dp[N])$ 的步骤，即收集子问题的解来解决原问题。

class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {//动规第一轮//dp[i][j] 表示从根部即0行0列到第i行第j列数字最小路径和//dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];int M = triangle.size();int N = triangle.back().size();vector<vector<int>> dp(M+1, vector<int>(N+1, 0) );//初始化两侧的值dp[0][0] = triangle[0][0];for(int i=1;i<M;++i){dp[i][0] = dp[i-1][0] + triangle[i][0];dp[i][triangle[i].size()-1] = dp[i-1][triangle[i-1].size()-1] + triangle[i].back();}//动态规划for(int i=1;i<M;++i){for(int j=1; j<triangle[i].size()-1; ++j){dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];}}//子问题求最优解int ans = dp[M-1][0];for(int k=1; k<N; ++k){ans = min(ans, dp[M-1][k]);}return ans;}
};

通过这个问题再次引出一个名词 最优子结构， 即原问题的最优解可以由子问题的最优解推导出来。

辨析：

那么，动态规划解决的问题必须是拥有重叠子问题和最优子结构。

分治法解决的问题是不重叠的。

1.3 最大连续子序列和

• https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
• https://leetcode.cn/problems/maximum-subarray/description/

这道题属于连续子串的问题。还是上面的思路：分治+动规。

dp【i】表示以i结尾的连续子数组的最大和。那么dp[i]就有两种思路：要么和前面一起组成连续子串，要么自己单独成立连续子串。

dp[i] = max{A[i],dp[i-1] + A[i]};
//初始化也很容易
dp[0] = A[0];

最后还要收集子问题的解

max(dp[0], dp[1], ..., dp[N])

1.4 最长不下降子序列

• https://leetcode.cn/problems/longest-continuous-increasing-subsequence/

这道题属于子序列的问题。还是上面的思路：分治+动规。

dp【i】表示以i结尾的最长不下降子序列。由于是子序列，不要求连续，那么第i个元素就可以和先前i-1个元素进行比较，整体复杂度O(N2)O(N^2)O(N2)

		int ans = -1;//记录最大的dp[i]for (int i = 1; i <= n; i++) {dp[i] = 1;//初始化for (int j = 1; j < i;j ++) {if(A[i] >= A[j] && (dp[j] + 1 > dp[i])) {dp[i] = dp[j] + 1;    }}ans = max(ans, dp[i]);}

对比，最长连续不下降子序列 https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

1.5 最长公共子序列

• https://leetcode.cn/problems/longest-common-subsequence/

求两个字符串的最长公共部分。两个字符串，容易想到二维dp数组。

dp[i][j]表示的是以第i个字符结尾的第一个字符串和以第j个字符结尾的第二个字符串之间的最长公共部分的长度。

类似：最长重复子数组 https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

1.6 最长回文子串

• https://leetcode.cn/problems/longest-palindromic-substring/description/

这道题有些不一样了，虽然是单个字符串，但是用一维dp数组反而不好解题。

考虑dp[i][j],表示第i个字符到第j个字符之间表示的字符串是否为回文串。

注意：这里经过两层抽象，一层是二维dp，另一层二维dp不是直接求解问题（它表示的区间字符串是否是回文串，而不是说当前区间的最长的回文串的长度），相当于前述的分治+动规

通过考虑区间长度的问题进行遍历，这其实又是一层抽象，不容易想到。

关于dp问题初始化和遍历的问题，令开博客填坑。

#include<cstdio>
#include<cstring>
const int maxn = 1010;
char S[maxn];
int dp[maxn][maxn];int main() {gets(S);int len = strlen(S), ans = 1;memset(dp,0,sizeof(dp));//边界for (int i = 0; i < len; i ++) {dp[i][i] = 1;if (i < len - 1) {if(S[i] == S[i+1]) {dp[i][i+1] = 1;ans = 2;//当前最长回文字符串}}}//状态转移方程for (int L = 3; L <= len; L++) {for (int i = 0; i + L - 1 < len; i++) {int j = i + L -1;if(S[i] == S[j] && dp[i+1][j-1] == 1) {dp[i][j] = 1;ans = L;}}}printf("%d\\n",ans);return 0;
}

对比，最长回文子序列 https://leetcode.cn/problems/longest-palindromic-subsequence/

1.7 背包问题

01背包和完全背包，重中之重~另外开博客填坑。

总结

算法笔记这里动态规划入门还是挺友好的，从斐波那契数列和数塔问题逐步了解动态规划的思想，我觉得很不错。后面字符串dp介绍得有点少了，导致问题看起来不是那么地连续。

现在总结一下字符串dp的套路：

2.1 字符串问题涉及两个概念：子串和子序列

一般来说，子串是连续的，子序列是不连续的。一道题可以出两道。

比如说

• 最大子串和
• 最大子序列和
• 最长不下降子串
• 最长不下将子序列
• 最长公共子串
• 最长公共子序列
• 最长回文子串
• 最长回文子序列

2.2 字符串dp设计的套路

当题目与子序列或子串相关时，可以考虑一下dp的设计

• 令dp【i】表示以s【i】结尾或开头的xxxx

二维dp涉及两个字符串

• 令dp【i】【j】表示以s【i】结尾，以t【i】结尾的xxx

二维dp只涉及一个字符串，比如求回文串

• 令dp【i】【j】表示s【i】至s【j】区间的xxx

2.3 关于dp【i】的下标

dp【i】可以表示恰好以i结尾，或者根据问题设计为前i个xxx

前者限定问题求解必须包含第i个元素，后面不作限定，只需要利用前i个元素求解即可。

最后，动态规划非常灵活，这里只涉及到了字符串动态规划的一小部分，还未涉及到编辑距离等题目，还需要多做题。本篇改名字符串动态规划入门比较好，哈哈哈。