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

62.不同路径

问题描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

解决方式：

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];//初始化数组第一行第一列全部填充1for(int i=0;i<n;i++){dp[0][i]=1;}for(int j=0;j<m;j++){dp[j][0]=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];}
}

63. 不同路径II

问题描述：

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

解决方式：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length; //行int n = obstacleGrid[0].length; //列int[][] dp = new int[m][n];int i=0,j=0;while(i<m){if(obstacleGrid[i][0]==1){break; //遇到障碍物直接退出循环}dp[i][0] = 1;i++;}while(j<n){if(obstacleGrid[0][j]==1){break;}dp[0][j] = 1;j++;}for(int a=1;a<m;a++){for(int b=1;b<n;b++){if(obstacleGrid[a][b]!=1){dp[a][b] = dp[a-1][b] + dp[a][b-1];}}}return dp[m-1][n-1];}
}

343整数拆分

问题描述：

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

解决方式：

class Solution {public int integerBreak(int n) {//dp[n] 表示拆分 n 的最大乘积int[] dp = new int[n+1];dp[1] = 1;dp[2] = 1;for(int i=3;i<=n;i++){for(int j=1;j<i;j++){/**在每次计算新的候选值时，与当前的 dp[i] 比较。如果新的候选值更大，则更新 dp[i]。 */dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}
}

96.不同的二叉搜索树

问题描述：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

解决方式：

class Solution {public int numTrees(int n) {//以 i 为根的 BST 数量 = 左子树的 BST 数量 × 右子树的 BST 数量int[] dp = new int[n+1];dp[0] = 1;//dp[i]是以j为根节点的情况总和for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){//计算每种 j 作为根节点时的 BST 数量，并累加到 dp[i]dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
}