63. 不同路径 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
//动规五部曲
//1.确定dp数组以及下标的含义
//到达坐标为(i,j)的格子的路径数目为dp[i][j]
//2.递推公式：dp[i][j] =
//obstacleGrid[i - 1][j] == 0 ? dp[i - 1][j] : 0
//+ obstacleGrid[i][j - 1] == 0 ? dp[i][j - 1] : 0;
//3.dp数组初始化，先初始化左上角，然后初始化上边和下边
//上边和左边初始化,初始化公式dp[0][j] = dp[0][j - 1];dp[i][0] = dp[i - 1][0]
//4.遍历顺序，从（1, 1）从左往右，按行遍历
//5.示例1推导：
//1 1 1
//1 0 1
//1 1 2
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
//3.先初始化左上角,是石头的话，直接返回0，因为出发点被堵了，哪也去不了
if(obstacleGrid[0][0] == 1) return 0;
vector< vector<int> > dp(m, vector<int>(n));
dp[0][0] = 1;
//3.把dp数组中最上边和最左边初始化，
//最上边一行：
for(int j = 1; j < n; j++)
{
//是石头置0，否则就是上一个位置的路径数
if(obstacleGrid[0][j] == 1) dp[0][j] = 0;
else dp[0][j] = dp[0][j - 1];
}
//最左边一行
for(int i = 1; i < m; i++)
{
if(obstacleGrid[i][0] == 1) dp[i][0] = 0;
else dp[i][0] = dp[i - 1][0];
}
//4.从（1，1）遍历
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
{
//递推公式
//是石头置0
if(obstacleGrid[i][j] == 1) dp[i][j] = 0;
else
{
dp[i][j] = (obstacleGrid[i - 1][j] == 0 ? dp[i - 1][j] : 0 )+ (obstacleGrid[i][j - 1] == 0 ? dp[i][j - 1] : 0);
}
}
}
return dp[m - 1][n - 1];
}
};
这道题目是昨天的升级版，有了很多坑。我一开始还是像上次一样初始化最上边和最左边，都设置为1，然后有石头的设置为0，结果就有样例通不过，发现上边和左边不仅有石头的话路径数是0，如果左边或者上边有石头挡路，那么后面的也都是0。所以这道题和上次最大的不同就是初始化，而且要做两次初始化。
还有一点就是，在遍历的过程中，遇到石头置0，不能初始化时把所有石头置0后面就不管了，不然有可能到后面遍历的时候，石头位置被赋值了而且不是0，那就错了。
343. 整数拆分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
//动规五部曲
//1.确认dp数组和下标的含义
//正整数i的拆分乘积最大为dp[i]
//2.确认递推公式：从1到i开始试，选取 只拆成两个 和 拆成大于两个 中较大的一个
//dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));//(dp[i - j])拆的项肯定 >= 2
//3.初始化dp数组：只用初始化dp[2] = 1 即可，dp[0]和dp[1] 本身就不能拆
//4.遍历顺序，从小数往大数遍历，即从前往后
//5.举例2推导 n = 10
//2 3 4 5 6 7 8 9 10
//1 2 4 6 9 12 18 27 36（2 * dp[8]）
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[2] = 1;
for(int i = 3; i <= n; i++)
{
//可以取i-2但不取i-1，因为如果取i-1那么就会出现dp[1]
for(int j = 1; j <= i - 2; j++)
{
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
};
别看代码很短，还挺难想的。主要难点就在于递推公式的推导。把数拆为几项是个问题，首先是拆成两个，其次是拆成多个，拆成多个的话就可以利用之前的值了，也就是dp[i - j]，不得不说，这个思路我一开始是真没想到。
还有要注意的就是初始化，初始化dp[2]就行，在遍历的时候遍历到 j = i -2 就可以了。