当前位置: 首页> 文旅> 文化 > 代码随想录算法训练营第三十四天 | 62.不同路径,63. 不同路径 II,343.整数拆分,96.不同的二叉搜索树

代码随想录算法训练营第三十四天 | 62.不同路径,63. 不同路径 II,343.整数拆分,96.不同的二叉搜索树

时间:2025/7/11 0:35:48来源:https://blog.csdn.net/qq_61552256/article/details/142307867 浏览次数:0次

三十四天打卡,今天后两题难一些,第三题分为把数拆成两部分或者多部分,第四题分析头节点的值从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();}
};
关键字:代码随想录算法训练营第三十四天 | 62.不同路径,63. 不同路径 II,343.整数拆分,96.不同的二叉搜索树

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: