62. 不同路径

题目描述:

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start”）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

问总共有多少条不同的路径？

dp 五步曲：

1. 定义dp数组、确定dp[i][j]含义
2. int dp = new intm;
3. dp[i][j]表示到达(i,j)路径的数量
4. 递推公式：dp[i][j]= dp[i][j]- 1 + dp[i][j];
5. 当前位置只能由其正上方和正左方过来
6. 初始化
7. 第一行、第一列全为 1
8. if (i == 0 || j == 0) dp[i][j]= 1;
9. 顺序：从上到下，从左到右
10. 打印dp日志

63. 不同路径 II

题目描述：

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径

这题和上题 62. 不同路径基本类似

区别在于两点：

1. 碰到障碍物时：dp[i][j] = 0
2. 初始化不同：如果第一行中间有障碍物了，则其后均不可达（其后dp0=0）；第一列，同理
3. 这里 carl哥初始化的相当巧妙
4. 循环终止条件，一旦遇到obstacleGridi == 1的情况就停止dpi的赋值1的操作
5. for (int i = 0; i < m && obstacleGrid[i][i] == 0; i++) dp[i][j] = 1;

343. 整数拆分

题目描述：

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

dp 五步曲：

1. 定义dp数组、确定dp[i]含义