尝试函数有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;
}
};