算法【从递归入手二维动态规划】

尝试函数有1个可变参数可以完全决定返回值，进而可以改出1维动态规划表的实现。同理，尝试函数有2个可变参数可以完全决定返回值，那么就可以改出2维动态规划的实现。

一维、二维、三维甚至多维动态规划问题，大体过程都是：

1.写出尝试递归。

2.记忆化搜索(从顶到底的动态规划)。

3.严格位置依赖的动态规划(从底到顶的动态规划)。

4.空间、时间的更多优化。

动态规划表的大小：每个可变参数的可能性数量相乘。

动态规划方法的时间复杂度：动态规划表的大小 * 每个格子的枚举代价。

二维动态规划依然需要去整理动态规划表的格子之间的依赖关系，找寻依赖关系，往往通过画图来建立空间感，使其更显而易见。然后依然是从简单格子填写到复杂格子的过程，即严格位置依赖的动态规划(从底到顶)。

二维动态规划的压缩空间技巧原理不难，会了之后千篇一律。但是不同题目依赖关系不一样，需要 很细心的画图来整理具体题目的依赖关系。最后进行空间压缩的实现。

能改成动态规划的递归，统一特征：决定返回值的可变参数类型往往都比较简单，一般不会比int类型更复杂。

从这个角度，可以解释带路径的递归（可变参数类型复杂），不适合或者说没有必要改成动态规化。题目2就是说明这一点的。

一定要写出可变参数类型简单（不比int类型更复杂），并且可以完全决定返回值的递归，保证做到 这些可变参数可以完全代表之前决策过程对后续过程的影响，再去改动态规划。

不管几维动态规划，经常从递归的定义出发，避免后续进行很多边界讨论，这需要一定的经验来预知。

下面通过一些题目来加深理解。

题目一

测试链接：https://leetcode.cn/problems/minimum-path-sum/

分析：这道题依旧是从递归到记忆化搜索到严格位置依赖到空间压缩，不过递归会超时，所以直接从记忆化搜索开始了。f方法求从下标i，j位置到右下角的和最小为多少。递归调用并采用记忆化搜索即可得到答案。代码如下。

class Solution {
public:int row;int column;int dp[200][200];void build(){for(int i = 0;i < row;++i){for(int j = 0;j < column;++j){dp[i][j] = -1;}}}int f(int i, int j, vector<vector<int>>& grid){if(dp[i][j] != -1){return dp[i][j];}int ans = -((1 << 31) + 1);if(j + 1 < column){ans = ans < f(i, j+1, grid) ? ans : f(i, j+1, grid);}if(i + 1 < row){ans = ans < f(i+1, j, grid) ? ans : f(i+1, j, grid);}dp[i][j] = ans == -((1 << 31) + 1) ? grid[i][j] : ans+grid[i][j];return dp[i][j];}int minPathSum(vector<vector<int>>& grid) {row = grid.size();column = grid[0].size();build();return f(0, 0, grid);}
};

从代码中可以看出这个题目的遍历方向以及递推公式，故可以写出严格位置依赖的动态规划。代码如下。

class Solution {
public:int row;int column;int dp[200][200];int minPathSum(vector<vector<int>>& grid) {row = grid.size();column = grid[0].size();for(int i = row-1;i >= 0;--i){for(int j = column-1;j >= 0;--j){int ans = -((1 << 31) + 1);if(j + 1 < column){ans = ans < dp[i][j+1] ? ans : dp[i][j+1];}if(i + 1 < row){ans = ans < dp[i+1][j] ? ans : dp[i+1][j];}dp[i][j] = ans == -((1 << 31) + 1) ? grid[i][j] : ans+grid[i][j];}}return dp[0][0];}
};

从代码中可以看出，只需使用一个一维数组滚动遍历即可，这样就可以得到空间压缩的代码。代码如下。

class Solution {
public:int row;int column;int dp[200];int minPathSum(vector<vector<int>>& grid) {row = grid.size();column = grid[0].size();dp[column-1] = grid[row-1][column-1];for(int i = column-2;i >= 0;--i){dp[i] = dp[i+1] + grid[row-1][i];}for(int i = row-2;i >= 0;--i){for(int j = column-1;j >= 0;--j){if(j + 1 < column){dp[j] = dp[j] < dp[j+1] ? dp[j] : dp[j+1];}dp[j] += grid[i][j];}}return dp[0];}
};

这个题目几种解法的递进和之前的一维递归很像，在后面的题目中就不会再出现完整的全部解法的代码了。

题目二

测试链接：https://leetcode.cn/problems/word-search/

分析：这个题一看就会想到深度优先搜索，也是一个递归。不过这种带路径的递归没有必要改成动态规划，所以当成深搜题目即可。代码如下。

class Solution {
public:int row;int column;bool f(int i, int j, int index, vector<vector<char>>& board, string word){if(index == word.size()){return true;}if(i < 0 || i >= row || j < 0 || j >= column || word[index] != board[i][j]){return false;}char temp = board[i][j];board[i][j] = 0;bool ans = f(i-1, j, index+1, board, word)|| f(i+1, j, index+1, board, word)|| f(i, j-1, index+1, board, word)|| f(i, j+1, index+1, board, word);board[i][j] = temp;return ans;}bool exist(vector<vector<char>>& board, string word) {row = board.size();column = board[0].size();for(int i = 0;i < row;++i){for(int j = 0;j < column;++j){if(f(i, j, 0, board, word)){return true;}}}return false;}
};

题目三

测试链接：https://leetcode.cn/problems/longest-common-subsequence/

分析：这道题目普通递归和记忆化搜索都会超时，所以给出严格位置依赖和空间压缩的解法。dp数组的含义是字符串text1前i个字符和字符串text2前j个字符的最长公共子序列长度。这里之所以用个数而不是下标，是避免多个边界讨论，用下标也可以求解，只是代码较为冗余。代码如下。

class Solution {
public:int length_1;int length_2;int dp[1001][1001] = {0};int longestCommonSubsequence(string text1, string text2) {length_1 = text1.size();length_2 = text2.size();for(int i = 1;i <= length_1;++i){for(int j = 1;j <= length_2;++j){if(text1[i-1] == text2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = dp[i-1][j] > dp[i][j-1] ?dp[i-1][j] : dp[i][j-1];}}}return dp[length_1][length_2];}
};

从代码中可以看出遍历方向从而得到空间压缩的解法。代码如下。

class Solution {
public:int length_1;int length_2;int dp[1001] = {0};int leftup1, leftup2;int longestCommonSubsequence(string text1, string text2) {length_1 = text1.size();length_2 = text2.size();for(int i = 1;i <= length_1;++i){leftup1 = 0;for(int j = 1;j <= length_2;++j){leftup2 = dp[j];if(text1[i-1] == text2[j-1]){dp[j] = leftup1 + 1;}else{dp[j] = dp[j] > dp[j-1] ? dp[j] : dp[j-1];}leftup1 = leftup2;}}return dp[length_2];}
};

其中，leftup1是保存即将可能被用到的左上角的dp值，leftup2是保存下一个可能被用到的左上角的dp值。

题目四

测试链接：https://leetcode.cn/problems/longest-palindromic-subsequence/

分析：这道题普通递归和记忆化搜索也是会超时，所以给出严格位置依赖和空间压缩的解法。dp数组的含义是从下标i到下标j中最长回文字序列的长度。代码如下。

class Solution {
public:int length;int dp[1000][1000] = {0};int longestPalindromeSubseq(string s) {length = s.size();for(int i = 0;i < length;++i){dp[i][i] = 1;}for(int i = length-2;i >= 0;--i){for(int j = i+1;j < length;++j){if(j == i+1){dp[i][j] = s[i] == s[j] ? 2 : 1;}else{if(s[i] == s[j]){dp[i][j] = 2 + dp[i+1][j-1];}else{dp[i][j] = dp[i+1][j] > dp[i][j-1] ?dp[i+1][j] : dp[i][j-1];}}}}return dp[0][length-1];}
};

从代码中可以看出遍历方向从而得到空间压缩的解法。代码如下。

class Solution {
public:int length;int leftdown1, leftdown2;int dp[1000] = {0};int longestPalindromeSubseq(string s) {length = s.size();if(length == 1){return 1;}if(length == 2){return s[0] == s[1] ? 2 : 1;}for(int i = length-1;i >= 0;--i){dp[i] = 1;leftdown1 = 0;for(int j = i+1;j < length;++j){leftdown2 = dp[j];if(j == i+1){dp[j] = s[i] == s[j] ? 2 : 1;}else{if(s[i] == s[j]){dp[j] = 2 + leftdown1;}else{dp[j] = dp[j] > dp[j-1] ?dp[j] : dp[j-1];}}leftdown1 = leftdown2;}}return dp[length-1];}
};

其中，leftdown1以及leftdown2和上一题的leftup含义基本一致，leftdown1是保存即将可能被用到的左下角的dp值，leftup2是保存下一个可能被用到的左下角的dp值。

题目五

测试链接：https://www.nowcoder.com/practice/aaefe5896cce4204b276e213e725f3ea

分析：下面给出记忆化搜索和严格位置依的解法。dp数组代表i个节点高度不超过j时有多少种方案。代码如下。

#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;
int n, m;
int dp[51][51];
void build(){for(int i = 0;i <= n;++i){for(int j = 0;j <= m;++j){dp[i][j] = -1;}}for(int i = 0;i <= m;++i){dp[0][i] = 1;}dp[1][0] = 0;for(int i = 1;i <= m;++i){dp[1][i] = 1;}dp[2][0] = 0;dp[2][1] = 0;for(int i = 2;i <= m;++i){dp[2][i] = 2;}
}
int f(int i, int j){if(dp[i][j] != -1){return dp[i][j];}int ans = 0;long long temp;for(int num = 0;num < i;++num){temp = (long long)f(num, j-1) * (long long)f(i-1-num, j-1);ans = (int)(((long long)ans + temp) % MOD);}dp[i][j] = ans;return ans;
}
int main(void){scanf("%d%d", &n, &m);build();printf("%d", f(n, m));
}

从代码中看出遍历方向，从而得到严格位置依赖的解法。代码如下。

#include <iostream>
#define MOD 1000000007
using namespace std;
int n, m;
int dp[51][51] = {0};
int main(void){scanf("%d%d", &n, &m);for(int i = 0;i <= m;++i){dp[0][i] = 1;}for(int i = 1;i <= m;++i){dp[1][i] = 1;}for(int i = 2;i <= m;++i){dp[2][i] = 2;}long long temp;for(int i = 3;i <= n;++i){for(int j = 2;j <= m;++j){for(int num = 0;num < i;++num){temp = (long long)dp[num][j-1] * (long long)dp[i-1-num][j-1];dp[i][j] = (int)(((long long)dp[i][j] + temp) % MOD);}}}printf("%d", dp[n][m]);
}

题目六

测试链接：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/

分析：这个题给出记忆化搜索的解法，这种带路径的题目没有改成严格位置依赖的必要。dp数组的含义为从ij下标位置一直递增的最大路径长度。代码如下。

class Solution {
public:int row;int column;int arr[5] = {0, -1, 0, 1, 0};int dp[200][200] = {0};int f(int i, int j, vector<vector<int>>& matrix){if(dp[i][j] != 0){return dp[i][j];}int len = 0;int x, y;for(int index = 0;index < 4;++index){x = i+arr[index];y = j+arr[index+1];if(x >= 0 && x < row && y >= 0 && y < column && matrix[i][j] < matrix[x][y]){len = len > f(x, y, matrix) ? len : f(x, y, matrix);}}dp[i][j] = len+1;return len+1;}int longestIncreasingPath(vector<vector<int>>& matrix) {row = matrix.size();column = matrix[0].size();int ans = 0;for(int i = 0;i < row;++i){for(int j = 0;j < column;++j){ans = ans > f(i, j, matrix) ? ans : f(i, j, matrix);}}return ans;}
};