深圳网站建房,个人网站制作手绘,石家庄网站制作网页,wordpress卖电子书62.不同路径
我的代码#xff08;报错#xff09; 写的过程中感到很迷惑的点#xff1a;①二维数组和这道题目的对应弄不清除#xff0c;m n的初始化 是 dp[m][n] 还是 dp[n][m] ②
class Solution {public int uniquePaths(int m, int n) {int[][]dp new int[m1][n1];d…62.不同路径
我的代码报错 写的过程中感到很迷惑的点①二维数组和这道题目的对应弄不清除m n的初始化 是 dp[m][n] 还是 dp[n][m] ②
class Solution {public int uniquePaths(int m, int n) {int[][]dp new int[m1][n1];dp[0][0] 0;dp[0][1] 1;dp[1][0] 1;for(int i1; im; i) {for(int j1; jn; j) {dp[i][j] dp[i-1][j] dp[i-1][j-1];}}return dp[m][n];}
}/*
自己解题的时候思考过程n-1 : 往右走的次数
m-1 : 往下走的次数 dp[i][j]到当前的位置有几种方法
dp[0][0] 0
dp[0][1] 1
dp[1][0] 1
dp[1][1] 2
dp[i][j] 的前一个状态是(1)他的左边dp[i-1][j]或者(1)dp[i-1][j-1]
dp[i][j] dp[i-1][j] dp[i-1][j-1];*/初始化出错这里初始化要覆盖到整个左列 和 横排
// 第0列dp[i][0] 表示到当前的位置有几种方法这一列都是只有一种for (int i 0; i m; i) {dp[i][0] 1;}// 第0行dp[0][i] 表示到当前的位置有几种方法这一行都是只有一种for (int i 0; i n; i) {dp[0][i] 1;}JAVA二维数组存储示意图 思考过程 (1) 确定dp数组以及下标的含义到当前的位置[i][j]有几种方法 dp[i][j] (2) 确定递推公式 dp[i][j] dp[i-1][j] dp[i][j-1]; (3) dp数组如何初始化 本题就栽在这一步了其实是要for循环 初始化一列和一排的 (4) 确定遍历顺序 从前到后 (5) 举例推导dp数组 (6) 打印 dp 数组 ac
class Solution {public int uniquePaths(int m, int n) {int[][]dp new int[m][n];for(int i0; im; i) {dp[i][0] 1;}for(int i0; in; i) {dp[0][i] 1;}for(int i1; im; i) {for(int j1; jn; j) {dp[i][j] dp[i-1][j] dp[i][j-1];}}return dp[m-1][n-1];}
}java
求二维数组长度
int m obstacleGrid.length;
int n obstacleGrid[0].length;63. 不同路径 II 推导公式 dp[i][j] dp[i-1][j] dp[i][j-1]; 如果[i][j]有障碍本来就走不了。 if(obs[i][j] 0) dp[i][j] dp[i-1][j] dp[i][j-1]; 初始化 如果第一行或者第一列有一个障碍物那么后面的都要初始化为0 出错
java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3at line 22, Solution.uniquePathsWithObstaclesat line 56, __DriverSolution__.__helper__at line 86, __Driver__.main因为dp从[1][1]走起
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][]dp new int[m][n];if(obstacleGrid[0][0] 1 || obstacleGrid[m-1][n-1] 1) {return 0;} //初始化for(int i0; im obstacleGrid[i][0]!1; i) {dp[i][0] 1;//中途如果有obstacleGrid[i][0]!0那就暂停循环Java初始化都赋了0}//初始化for(int j0; jn obstacleGrid[0][j]!1; j) {dp[0][j] 1;}for(int i1; im; i) { //这里写了0是错误的for(int j1; jn; j) {dp[i][j] (obstacleGrid[i][j]0?(dp[i][j-1]dp[i-1][j]):0);}}return dp[m-1][n-1];}
}//我的思考
// obstacleGrid[i][j] 1 此处有障碍物走不了
// obstacleGrid[i][j] 0
// dp[i][j] dp[i-1][j] dp[i][j-1]
// 如果 obstacleGrid[i-1][j] 1前一种状态就不能是dp[i-1][j]dp[i][j] dp[i][j-1]
// 如果 obstacleGrid[i][j-1] 1前一种状态就不能是dp[i][j-1]dp[i][j] dp[i-1][j]
343. 整数拆分 没啥思路 力扣解题思路 ① 尽可能拆成相同的数字当所有拆分出的数字相等时乘积最大。② 最优拆分数字为 3 。
数学方法
class Solution {public int integerBreak(int n) {if(n 3) return n - 1;int a n / 3, b n % 3;if(b 0) return (int)Math.pow(3, a);if(b 1) return (int)Math.pow(3, a - 1) * 4;return (int)Math.pow(3, a) * 2;}
}动态规划 有点没看懂
96. 不同的二叉搜索树
