代码随想录算法训练营第三十四天 | 62.不同路径，63. 不同路径 II，343.整数拆分，96.不同的二叉搜索树
三十四天打卡，今天后两题难一些，第三题分为把数拆成两部分或者多部分，第四题分析头节点的值从1到n - 1
62.不同路径
题目链接
做题过程
dp[i][j]：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
动态规划
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>dp(m, vector<int>(n, 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.back().back();}
};
63.不同路径Ⅱ
题目链接
解题思路
- 跟上一题比，初始化需多一步，状态转移公式是一样的
动态规划
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, 1));for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1) {while (i < m) {dp[i++][0] = 0;}}}for (int j = 0; j < n; j++) {if (obstacleGrid[0][j] == 1) {while (j < n) {dp[0][j++] = 0;}}}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) {dp[i][j] = 0;} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp.back().back();}
};
343.整数拆分
题目链接
解题过程
- 没想到dp思路，定义dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
- i : [3, n]
j : [1, n - 2] ，其中n - 1和1是等价的，比如5可以拆分成1+4和4+1
dp[i] = max(dp[i], j * (i - j), dp[j] * (i - j))
在j遍历的过程中更新dp[i]的最大值，j * (i - j)是把i拆分为两部分，dp[j] * (i - j)是把i拆分为三部分及以上
动态规划
class Solution {
public:int integerBreak(int n) {if (n == 2) return 1;vector<int>dp(n + 1);for (int i = 3; i <= n; i++) {for (int j = 1; j <= i - 2; j++) {dp[i] = max(dp[i], max(j * (i - j), dp[j] * (i - j)));}}return dp.back();}
};
96.不同的二叉搜索树
题目链接
解题过程
-
用动态规划思路做出来
-
dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
知识点
-
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[i] += dp[j] * dp[i - j - 1];
动态规划
class Solution {
public:int numTrees(int n) {vector<int>dp(n + 1);dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 0; j <= i - 1; j++) {dp[i] += dp[j] * dp[i - j - 1];}}return dp.back();}
};