继续动态规划的基础题目。
题目：不同路径
62. 不同路径 - 力扣（LeetCode）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
题目分析：
按照动规五部曲来分析：
确定dp数组（dp table）以及下标的含义
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
确定递推公式
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。
那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
dp数组的初始化
如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
那么代码就很好写出来了
public class Solution {
public int UniquePaths(int m, int n) {
int[,] dp=new int[m,n]; //确定dp数组
//初始化
for(int i=0;i<m;i++){
dp[i,0]=1;
}
for(int i=0;i<n;i++){
dp[0,i]=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];
}
}题目：不同路径 II
63. 不同路径 II - 力扣（LeetCode）
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
题目分析：
比上一题多了一个不可走的条件，那么我们在初始化和遍历的时候加个条件就可以了，其他部分和上一题一样的
public class Solution {
public int UniquePathsWithObstacles(int[][] obstacleGrid) {
int m=obstacleGrid.Length;
int n=obstacleGrid[0].Length;
if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return 0;//起点或终点不可达
int[,] dp=new int[m,n];
for(int i=0;i<m&&obstacleGrid[i][0]==0;i++){
dp[i,0]=1;
}
for(int i=0;i<n&&obstacleGrid[0][i]==0;i++){
dp[0,i]=1;
}
//遍历
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(obstacleGrid[i][j]==0){
dp[i,j]=dp[i-1,j]+dp[i,j-1];
}
}
}
return dp[m-1,n-1];
}
}题目：整数拆分
343. 整数拆分 - 力扣（LeetCode）
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
题目分析：
这一题的dp[i]，表示i拆分之后乘积的最大值，如何得到这个dp[i]
先看看递推过程,从下面这些取值来看，假如我把i拆成k个数，那么最大值是 k*(i-k)
2：1+1 1*1=2；k=2
3：1+2 1*2=2; k=2
4: 2+2 2*2=4; k=2
5: 2+3 2*3=6; k=2
除此之外，还有j * dp[i - j]，相当于是拆分(i - j)。那么最大值就是两个中的一个。
需要注意的是
j*(i-j):
将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
j * dp[i - j]：
将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]
public class Solution {
public int IntegerBreak(int n) {
int[] dp=new int[n+1];
dp[2]=1;//dp[0]和dp[1]没意义
for(int i=3;i<=n;i++){
for(int j=1;j<=i/2;j++){//这里优化了，原本是j<i-1
dp[i] = Math.Max(dp[i],Math.Max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
}最后一题的递推公式比较复杂，建议找更详细的解析看
对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。
代码随想录 (programmercarl.com)