62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
- 输入：m = 3, n = 7
- 输出：28
思路
按照动规解题步骤：
- dp数组及其下标含义：从
(0,0)到(i,j)共有不同的路径dp[i][j]条 - 递推公式：在网格上移动，求
dp[i][j]只能从两个方向推导过来，即dp[i - 1][j] & dp[i][j - 1]，因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - 数组初始化：受网格边框限制，沿着墙走不可能有第二种路径，因此
dp[0][j]=dp[i][0]=0 - 遍历顺序：
dp[i][j]取决于其左侧和上方，因此从左至右一层一层遍历即可 -
举例推导：推导结果如下所示
从一维的爬楼梯到二维的网格移动，其本质仍是斐波那契数列的上阶段状态求和问题，但初始化的步骤有很大不同。
代码实现
二维数组的定义：
dp(m, vector)表示二维动态数组dp的外层大小为m，m个元素每个都是一个vector<int>，vector<int>(n,0)则表示内层有n个元素，且每个元素的初始值都是0。
vector<vector<int>> dp(m, vector<int>(n, 0));
此时
int m = dp.size(); // 行数
int n = dp[0].size(); // 列数
代码实现如下，重点在于场景下的数组初始化，对靠墙路径的赋值1处理，使得其它位置可以很轻易地靠上方和左侧元素计算出自己的值：
class Solution {
public:
int uniquePaths(int m, int n) {
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];
}
};
第一次写报错，原因在于遍历循环时从
i,j=0开始，但循环体内部访问了i,j的上方和左侧元素，因此出现越界。
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
思路
本题相较于上题多了一个障碍物的限制，实际上这只影响到数组初始化这一个部分，首先障碍物本身所在位置(a,b)，其可到达路径dp[a][b]必定为0；此外，若障碍物位于靠墙路径上(c,0)，由于只能向右或向下移动，因此障碍物及其身后位置可达路径dp[c][0]～dp[m][0]也必定全为0
- dp数组及其下标含义：同理，从
(0,0)到(i,j)共有不同的路径dp[i][j]条 - 递推公式：同理，在网格上移动，求
dp[i][j]只能从两个方向推导过来，即dp[i - 1][j] & dp[i][j - 1]，因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - 数组初始化：受网格边框限制，沿着墙走不可能有第二种路径，因此
dp[0][j]=dp[i][0]=1。此外，障碍物所在位置，以及靠墙障碍物身后位置均为0 - 遍历顺序：
dp[i][j]取决于其左侧和上方，因此从左至右一层一层遍历即可
代码实现
要注意本题的输入不再是一个网格的行列数(m, n)，而是一个实际的网格矩阵，以便其中有障碍物的位置被标记为1。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n,0));
for(int i=0; i<m && obstacleGrid[i][0]==0; i++) dp[i][0] = 1;
for(int j=0; j<n && obstacleGrid[0][j]==0; j++) dp[0][j] = 1;
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if (obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
初始化时已将整个dp置为0，因此遇到障碍物及其身后位置的非法位置时，直接跳过不处理即可，无需额外操作
343. 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
思路
思考如何将一个拆分和求乘积的问题建模为动态规划，就要思考最终结果与其上一状态的关系，任意整数的和拆分乘积，只能是某两个小于它的数或其进一步拆分，因此很容易想到用dp[i-j]代表了i-j能拆分出的最大乘积，再乘以j
- dp数组及其下标含义：
dp[i]的结果为最终输出，因此可以定义为：分拆数字i，可以得到的最大乘积为dp[i] -
递推公式：将整数n拆分成两个或以上数字的和，这里可以分成两种情况：
- 两个数字的和：
j*(n-j)，j是一个从1开始遍历的值，以找出最大乘积 - 两个以上：
j*dp[n-j]，即将(n-j)再拆分，表示(i-j)分拆所能得到的最大乘积 - 因此递归公式如下，内层max()用于判定本轮
j的两种拆分方式哪个更大，外部max用于判定所有j遍历记录中的最大值dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
- 两个数字的和：
- 数组初始化：拆分成至少两个整数的和，因此
n=0和n=1在该问题下没有意义，直接定义dp[2]=1即可 - 遍历顺序：爬楼梯的遍历顺序一定是从前向后遍历的
- 举例推导：
代码实现
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1);
dp[2]=1;
for(int i=3; i<=n; i++){
for(int j=1; j<=i-1; j++){
dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]));
}
}
return dp[n];
}
};
后记
- 动态规划的基本问题，大多直接取dp数组的最终结果为输出，因此
dp[i]的意义通常就是输出的意义，此时再代入去分析i的含义即可 - dp[n]代表n的最终结果，但数组下标从0开始，因此dp[n]的实际存储位置为n+1，所以在定义数组时要考虑多定义一个长度。
