代码随想录Day34 | 62.不同路径,63.不同路径II,343.整数拆分,96.不同的二叉搜索树

代码随想录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];}
}