代码随想录算法训练营 | 动态规划 part02

62. 不同路径

62. 不同路径

class Solution {
public:int uniquePaths(int m, int n) {// 记录到达每个格子的路径数vector<vector<int>> dp(m, vector<int>(n));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0 && j == 0) { // 起点dp[0][0] = 1;} else if (i == 0 && j > 0) { // 上边界dp[i][j] = dp[i][j - 1];} else if (i > 0 && j == 0) { // 左边界dp[i][j] = dp[i - 1][j];} else if (i > 0 && j > 0) {dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}}return dp[m - 1][n - 1];}
};

将dp table压缩为一维数组

class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n);dp[0] = 1; // 对左边界的限制for (int i = 0; i < m; i++) {for (int j = 1; j < n; j++) {dp[j] += dp[j - 1]; // dp[j]上面网格；dp[j - 1]左面网格}}return dp[n - 1];}
};

63. 不同路径 II

63. 不同路径 II

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();// 记录到达每个网格的路径数vector<vector<int>> dp(m, vector<int>(n));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (obstacleGrid[i][j] == 1) { // 当前网格有障碍物，不可以到达continue;}if (i == 0 && j == 0) { // 起点dp[0][0] = 1;}if (j > 0) {dp[i][j] += dp[i][j - 1];}if (i > 0) {dp[i][j] += dp[i - 1][j];}1}}return dp[m - 1][n - 1];}
};

空间优化

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();// 记录到达当前行左边第一个网格 和 上一行(除第一个外)的网格的路径数vector<int> dp(n);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (obstacleGrid[i][j] == 1) { // 当前网格有障碍物，不可以到达dp[j] = 0;} else if (j == 0) { // 起点dp[j] = 1;} else if (j > 0) {dp[j] += dp[j - 1];}}}return dp[n - 1];}
};

343. 整数拆分

343. 整数拆分
当 n≥2 时，可以拆分成至少两个正整数的和。
设 这两个正整数分别是 x 和 n−x，对于 x 和 n−x （大于等于2时）也可以继续拆分成至少两个正整数的和，也可以不拆分。
所以一个正整数对应的最大乘积 取决于 拆分出的数 和 这个数对应的最大乘积；
举个例子：对于 n = 6 时

x	n-x	x的最大乘积	n-x的最大乘积	6的一次拆分x*(n-x)	拆x x的最大乘积*(n-x)	拆n-x x*(n-x)的最大乘积	两个都拆 x的最大乘积*(n-x)的最大乘积	6对应的最大乘积	备注
1	5	1	6	5	x不能拆	6	x不能拆	6
2	4	1	4	8	4	8	4	8
3	3	2	2	9	6	6	4	9

0 和 1不能拆分，就取他们本身的值；
用数组dp存储每一个数字的最大乘积；下标i对应数字i;

class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[1] = 1; dp[2] = 1;for (int i = 3; i < n + 1; i++) {// 首次拆成 2 个整数 j 和 i-j; j 的范围为[1, i/2]for (int j = 1; j <= i / 2; j++) {// 每次拆分更新dp[i]dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));}}return dp[n];}
};