第九章 动态规划 Part 02

今天开始逐渐有了动态规划的感觉了。前两题 不同路径非常适合进阶，大家可以好好研究一下。

---

详细布置

62. 不同路径

这道题掌握动态规划的方法就可以了。虽然数论方法也能解决问题，但有些非主流且很难想到。

题目链接
核心思想：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
视频讲解：B站视频链接
代码和思路还是比较好理解的，但是最大的问题还是

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];}
};

使用一维数组去解决，思路也非常巧妙，相当于，先确定第一列，然后dp[i] += dp[i - 1];即dp[i] =dp[i]+ dp[i - 1];。其实dp[i]相当于dp[i][j-1]，相当于左边哪一个，dp[i - 1]相当于dp[i - 1][j]，相当于上一行的。思路非常巧妙。

class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n);for (int i = 0; i < n; i++) dp[i] = 1;for (int j = 1; j < m; j++) {for (int i = 1; i < n; i++) {dp[i] += dp[i - 1];}}return dp[n - 1];}
};

二叉树的方法，没想到。根节点：代表起始位置。左子节点：代表向下移动一步。右子节点：代表向右移动一步。叶节点：代表到达终点的所有可能位置。
对于一个 m x n 的网格，二叉树的高度为 m + n - 1（因为需要 m-1 次向下移动和 n-1 次向右移动），并且树的宽度（在任意层的最大节点数）将从 1 增加到 m+n-1。二叉树

class Solution {
private:int dfs(int i, int j, int m, int n) {if (i > m || j > n) return 0; // 越界了if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);}
public:int uniquePaths(int m, int n) {return dfs(1, 1, m, n);}
};

---

63. 不同路径 II

题目链接
视频讲解：B站视频链接

这题核心思想就是，如果有障碍，就把当前位置dp值置0。思路很简单，但是写代码时很容易出问题，首先，我直接dp=obstacleGrid()。方便快捷，后来发现不行，因为空路径是0，有物体是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];}
};

---

343. 整数拆分（可跳过）

这道题的思路并不容易想到，建议在第一遍学习时可以跳过。如果你学有余力，推荐看视频理解一下。

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 / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}return dp[n];}
};

这题看着挺难的，结果发现居然是这么简单。就是层层迭代，然后层层循环，找出和之前的最大值。一层层的找 dp[i - j] * j的最大值，不断的遍历查值。思路还是比较清晰。 想明白了这个就可以：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
题目链接
视频讲解：B站视频链接

贪心算法也很好理解，其实感觉自己最开始的想法就是贪心算法，4>2*2, m<(m-2)*2,
选择 3 作为最优拆分因子而不是 2 是因为通过数学推导可以证明，但是我也看不太懂。不太理解。

class Solution {
public:int integerBreak(int n) {if (n == 2) return 1;if (n == 3) return 2;if (n == 4) return 4;int result = 1;while (n > 4) {result *= 3;n -= 3;}result *= n;return result;}
};

知道这个，代码就好写了呢。

---

96. 不同的二叉搜索树（可跳过）

本题的思路也比较复杂，建议在一刷时跳过。如果你学有余力，推荐看视频理解。


重点是看上面的图，把顺序推一遍
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

同理dp[4] = dp[3] * dp[0] + dp[2] * dp[1] + dp[1] * dp[2]+ + dp[0] * dp[3].如此，代码就很好写了

class Solution {
public:int numTrees(int n) {vector<int>nums(n+1,0);nums[0]=1;nums[1]=1;for(int i=2;i<=n;i++)for(int j=0;j<i;j++)nums[i]+= nums[j]*nums[i-j-1];return nums[n];}
};

题目链接
视频讲解：B站视频链接

---

通过这几道题，我们逐渐加深对动态规划的理解。接下来会继续学习更复杂的动态规划问题。