易旅游网站建设,网站首页的重要性,厨房装修图片,几十张照片合成视频代码随想录Day34 | 62.不同路径,63.不同路径II,343.整数拆分,96.不同的二叉搜索树
62.不同路径
动态规划第二集#xff1a;
比较标准简单的一道动态规划#xff0c;状态转移方程容易想到
难点在于空间复杂度的优化#xff0c;详见代码
class Solution {public int uniq…代码随想录Day34 | 62.不同路径,63.不同路径II,343.整数拆分,96.不同的二叉搜索树
62.不同路径
动态规划第二集
比较标准简单的一道动态规划状态转移方程容易想到
难点在于空间复杂度的优化详见代码
class Solution {public int uniquePaths(int m, int n) {// 标准的动态规划int[][] dp new int[m 1][n 1];// 初始化时多加了一行一列方便初始化dp[1][0] 1;for (int i 1; i dp.length; i) {for (int j 1; j dp[0].length; j) {// 状态转移方程dp[i][j] dp[i][j - 1] dp[i - 1][j];}}return dp[m][n];}
}class Solution {public int uniquePaths(int m, int n) {// 标准的动态规划,空间优化版int[] dp new int[n 1];dp[1] 1;for (int i 1; i m; i) {for (int j 2; j n; j) {// 状态转移方程// 只需要第 i 行与第 i-1 行的数据// dp[j - 1]已更新是第 i 行的数据// dp[j]未更新是第 i-1 行的数据dp[j] dp[j - 1] dp[j];}}return dp[n];}
}63.不同路径II
相比上题只多了一个障碍的判断
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;// 空间优化思路同62题int[] dp new int[n 1];dp[1] 1;for (int i 1; i m; i) {for (int j 1; j n; j) {// 处理障碍情况if (obstacleGrid[i - 1][j - 1] 1)dp[j] 0;// 状态转移方程else dp[j] dp[j - 1] dp[j];}}return dp[n];}
}343.整数拆分
动态规划问题相对简单想清楚状态转移方程就好详见代码注释
class Solution {public int integerBreak(int n) {// dp[i] 的定义是 对 i 进行划分后的最大乘积int[] dp new int[n 1];dp[2] 1;// 动态规划for (int i 3; i n; i) {// 循环进行划分for (int j 1; j i / 2; j) {// 状态转移方程// j * dp[i - j] 相当于是 在 i-j 中进行了多次划分// j * (i - j) 是只划分一次dp[i] Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));}}return dp[n];}
}96.不同的二叉搜索树
动态规划
要注意到二叉树种类数目 左子树种类数目 * 右子树种类数目
class Solution {public int numTrees(int n) {// dp[i]定义为 i个节点时互不相同的BST的种类数int[] dp new int[n 1];// 初始化0个节点时只有一种dp[0] 1;for (int i 1; i n ; i) {// 循环选择根节点为 jfor (int j 1; j i; j) {// dp[j - 1]为左子树种类数dp[i - j]为右子树种类数// 左右数目相乘即为根节点为 j 时的种类数// 累加到 dp[i] 上dp[i] dp[j - 1] * dp[i - j];}}return dp[n];}
}
