一、动态规划与贪心的区别
动态规划（Dynamic Programming），使用解决具有很多重叠子问题的问题。动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的
二、动态规划解题步骤
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式（有时候是递推公式决定了dp数组如何初始化）
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
注意：对于递推数组初始化部分，我们要直接返回，以防止初始化部分越界。如一个dp数组要从[0]初始化到[m],那么当传入的参数i属于[0, m]时候就要直接返回。
三、简单例题
509,70,746
四、路径问题
1、无障碍路径问题
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
其中起点坐标为（0,0）；终点坐标为（m-1,n-1）问总共有多少条不同的路径？
1)dp数组和下标含义
dp[i][j]的定义为：机器人从(0 , 0) 位置触发，到(i ，j)的总路径数
2）递推公式（状态转移方程）
dp[i][j]可以从两个状态转移过来：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
3）初始化方法
从起点到达最上面一排的路径只有1条：for (int i = 0; i < m; i++) dp[i][0] = 1;
从起点到达最左面一列的路径只有1条：for (int j = 0; j < n; j++) dp[0][j] = 1;
4）遍历顺序
dp[i][j]都是从其上方和左方推导而来，而我们又初始化了第一层和最左边的一列，那么从左到右一层一层遍历就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
class Solution {
public:
int uniquePaths(int m, int n) {
/---初始化dp数组---/
vector<vector<int>> dp(m, vector<int>(n, 0)); //注意这里固定大小二维数组初始化方法
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
/---遍历，递推公式---/
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
可以将二维数组压缩成一维数组
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n);
for (int i = 0; i < n; i++) dp[i] = 1;
for (int j = 1; j < m; j++) {
for (int i = 1; i < n; i++) {
dp[i] += dp[i - 1];
}
}
return dp[n - 1];
}
};
2、有障碍路径问题
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
1）dp数组和下标含义
dp[i][j]的定义为：机器人从(0 , 0) 位置触发，到(i ，j)的总路径数；如果（i，j）是障碍物，则dp[i][j] = 0
2）递推公式（状态转移方程）
如果（i，j）不是障碍，则dp[i][j]可以从两个状态转移过来：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，而障碍物处的dp值为0，这意味着不能从障碍物处到达该点
如果（i，j）是障碍，则dp[i][j] = 0，因为没有路径可以到障碍内
3）初始化方法
从起点到达最上面一排的路径只有1条，如果遇到了障碍，障碍后面的坐标路径均为0，被障碍堵住了且不能向上走，过不来
从起点到达最左面一排的路径只有1条，如果遇到了障碍，障碍后面的坐标路径均为0，被障碍堵住了且不能向上走，过不来
4）遍历顺序
dp[i][j]都是从其上方和左方推导而来，而我们又初始化了第一层和最左边的一列，那么从左到右一层一层遍历就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
/-----初始化dp数组-----/
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int pathInit = 1; //第一行dp数组
for(int i = 0; i < m; i++){
if(obstacleGrid[i][0] == 1){
pathInit = 0;
}
dp[i][0] = pathInit;
}
pathInit = 1; //第一列dp数组
for(int j = 0; j < n; j++){
if(obstacleGrid[0][j] == 1) pathInit = 0;
else dp[0][j] = pathInit;
}
/----遍历dp数组，递推公式---/
for(int i =1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 1) dp[i][j] = 0;
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
3、整数拆分
343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
1）dp数组和下标含义
dp[i]的定义为：整数i的最大拆分乘积
2）递推公式（状态转移方程）
对于dp[i]从1遍历j，比较
(i - j) * j（只拆分成j和i-j）和dp[i - j] * j（拆分成j和dp[i-j],dp[i-j]会进一步拆分）- 取全部遍历过程中最大的
即在单次循环中在三者中取最大的：
for(int j = 1; j < i; j++){ dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])); }
3）初始化方法
dp[0] 和dp[1]无意义，不用初始化。由于dp[i]只依赖于dp[2]~dp[i-1],因此初始化dp[2] = 1就可以
4）遍历顺序
按照递推公式，应该从左往右遍历
class Solution {
public:
int integerBreak(int n) {
/-----dp数组初始化-----/
vector<int> dp(n + 1);
dp[2] = 1;
/-----遍历，递推公式-----/
for(int i = 3; i < n + 1; i++){
for(int j = 1; j < i; j++){
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
};
4、不同的二叉树
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
1）dp数组和下标含义
dp[i]的定义为：1-i节点构成的二叉搜索树数量
2）递推公式（状态转移方程）
首先我们要明确一点：
题目中给定的二叉搜索树元素为1-n的意思是没有重复元素，而1-n个元素中，任意相同个元素能够构成的二叉搜索树数量和结构是一致的(如[1, 2, 3]和[1,25,36]都能构成5颗结构相同的二叉搜索树)，即此时二叉搜索树的数量仅与构成树的节点数量有关，而与具体节点的数值无关
对于dp[i]，如果我们已知dp[0]~dp[i-1]。dp[i]中一定有一个节点作为头节点，剩余的[i-1]个节点分别组成左子树和右子树，对于每一种拆分，共有dp[左子树数量]*dp[右子树数量]种二叉搜索树结构，因此递推公式为:
for(int j = 0; j < i; j++) {dp[i] += dp[j] * dp[i - 1 - j];}
3）初始化方法
dp[0] = 1， dp[1] = 1
4）遍历顺序
按照递推公式，应该从左往右遍历
5）推导dp数组（用于debug）
class Solution {
public:
int numTrees(int n) {
/-----初始化dp数组-----/
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
/-----遍历，递推数组-----/
for(int i = 2; i < n + 1; i++){
for(int j = 0; j < i; j++){
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}
};
|