网站建设制作流程,大悟县城乡建设局网站,宝安网站制作网站建设,那家建设网站p2p公司最好62.不同路径
和上楼梯相同#xff0c;机器人只可以向右向下移动。所以在位置[i,j]有两种情况#xff0c;一种从[i-1, j]向右移动到达当前位置#xff0c;或者从[i, j-1]向下移动到当前位置。所以到达当前位置的方法数量就等于到达[i, j-1]和到达[i-1, j]的方法数量的和。 简…62.不同路径
和上楼梯相同机器人只可以向右向下移动。所以在位置[i,j]有两种情况一种从[i-1, j]向右移动到达当前位置或者从[i, j-1]向下移动到当前位置。所以到达当前位置的方法数量就等于到达[i, j-1]和到达[i-1, j]的方法数量的和。 简单~ 二维dp数组
dp数组及下标含义 dp[i][j]表示从[0,0]到达[i,j]的方法数量递推公式dp[i][j] dp[i-1][j] dp[i][j-1]dp数组如何初始化dp[][0]和dp[0][]都初始化为1最上面那一行的位置只有一种方式就是从[0,0]一直向左移动最左边那一列位置到达方式只有一种方式就是从[0,0]一直向下移动。遍历顺序从上往下从左往右打印dp数组
class Solution {
public:int uniquePaths(int m, int n) {if(m 1 || n 1) return 1;vectorvectorint dp(m, vectorint(n));for(int i 0; i m; i){for(int j 0; j n; j){if(i0 || j0){dp[i][j] 1;//dp数组初始化} else{dp[i][j] dp[i-1][j]dp[i][j-1];}}}return dp[m-1][n-1];}
};class Solution {public int uniquePaths(int m, int n) {if(m 1 || n 1){return 1;}else{int[][] dp new int[m][n];for(int i 0; i m; i){for(int j 0; j n; j){if(i0 || j 0){dp[i][j] 1;}else{dp[i][j] dp[i-1][j]dp[i][j-1];}}}return dp[m-1][n-1];}}
}class Solution(object):def uniquePaths(self, m, n)::type m: int:type n: int:rtype: intif m 1 or n 1:return 1dp [[0]*n]*mfor i in range(m):for j in range(n):if i 0 or j 0:dp[i][j] 1else:dp[i][j] dp[i-1][j] dp[i][j-1]return dp[m-1][n-1]参考文章
https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
63. 不同路径 II
和不同路径相同。就是初始化和递推公式需要改变一下。 NOTE如果[0,0]或者[m, n]处有障碍物直接返回0。 二维dp数组
dp数组及下标含义 dp[i][j]表示从[0,0]到达[i,j]的方法数量递推公式加个条件语句if obj[i][0]0: dp[i][j] dp[i-1][j] dp[i][j-1] else: dp[i][j]0dp数组如何初始化遍历进行初始化第一行for(int i 0; i m obj[i][0]0; i) dp[i][0]1//如果遇到障碍物就无法向右移动后面的方法数都为0第一列同理。遍历顺序从上往下从左往右打印dp数组
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1) return 0;vectorvectorint dp(m, vectorint(n, 0));for(int i 0; i m obstacleGrid[i][0] 0; i) dp[i][0] 1;for(int j 0; j n obstacleGrid[0][j] 0; j) dp[0][j] 1;for(int i 1; i m; i){for(int j 1; j n; j){if(obstacleGrid[i][j] 0) dp[i][j] dp[i-1][j] dp[i][j-1];}}return dp[m-1][n-1];// int m obstacleGrid.size();// int n obstacleGrid[0].size();// if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1) return 0;// vectorvectorint dp(m, vectorint(n, 0));// for(int j 0; j n; j){// if(obstacleGrid[0][j]1) break;// else dp[0][j] 1;// }// for(int i 0; i m; i){// if(obstacleGrid[i][0]1) break;// else dp[i][0] 1;// }// for(int i 1; i m; i){// for(int j 1; j n; j){// if(obstacleGrid[i][j]0){// dp[i][j] dp[i-1][j] dp[i][j-1];// }// }// }// return dp[m-1][n-1];}
};class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1) return 0;int[][] dp new int[m][n];//初始化for(int i 0; i m obstacleGrid[i][0]0; i){dp[i][0] 1;}for(int j 0; j n obstacleGrid[0][j]0; j){dp[0][j] 1;}for(int i 1; i m; i){for(int j 1; j n; j){if(obstacleGrid[i][j] 0){dp[i][j] dp[i-1][j] dp[i][j-1];}else dp[i][j] 0;}}return dp[m-1][n-1];}
}class Solution(object):def uniquePathsWithObstacles(self, obstacleGrid)::type obstacleGrid: List[List[int]]:rtype: intm len(obstacleGrid)n len(obstacleGrid[0])if(obstacleGrid[0][0] 1 or obstacleGrid[m-1][n-1] 1):return 0dp [[0] * n for _ in range(m)]#注意这个初始化for i in range(m):if(obstacleGrid[i][0]1):breakdp[i][0] 1for j in range(n):if(obstacleGrid[0][j]1):breakdp[0][j] 1for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] 1:dp[i][j] 0else:dp[i][j] dp[i-1][j] dp[i][j-1]return dp[m-1][n-1]参考文章
https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html
343. 整数拆分 可跳过
dp数组及下标含义 dp[i]对i进行拆分拆分之后得到的最大乘积为dp[i]递推公式从0到i/2(可以取到因为拆分一个数我们比较的是dp[i],j*(i-j)和jdp[i-j]就是对i-j进一步拆分。其中j(i-j)是中间对称的然后jdp[i-j]中dp[i-j]包含i-j小的拆分方式)遍历jdp[i] max(j(i-j), j*dp[i-j],dp[i]。求不同数据拆分方式下的最大乘积所以遍历j的时候要保存dp[i]当前最大值。dp数组如何初始化0,1无法拆分没有意义都初始化为0dp[2]1遍历顺序从前往后打印dp数组
class Solution {
public:int integerBreak(int n) {vectorint dp(n1);dp[0] 0; dp[1] 0; dp[2] 1;//初始化for(int i 3; i n; i){for(int j 1; j i/2; j){//注意这里有等于dp[i] max(dp[i], max(j*dp[i-j], j*(i-j)));//求的dp[i]最大值在j循环的时候要保存其中最大值}}return dp[n];}
};class Solution {public int integerBreak(int n) {int[] dp new int[n1];dp[0] 0; dp[1] 0; dp[2] 1;//dp数组初始化for(int i 3; i n; i){for(int j 1; j i/2; j){dp[i] Math.max( dp[i] , Math.max(j*(i-j), j*dp[i-j]));}}return dp[n];}
}class Solution(object):def integerBreak(self, n)::type n: int:rtype: intdp [0]*(n1)#dp数组初始化dp[0] 0 dp[1] 0dp[2] 1for i in range(3, n1):for j in range(1, i/21):dp[i] max(dp[i], max(j*(i-j), j*dp[i-j]))return dp[n]参考文章
https://www.programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
96.不同的二叉搜索树 可跳过
不同二叉搜索树固定头节点二叉搜索树就是左子树的肿瘤*右子树的种类。对于给定n个节点可以组成的二叉搜索树的种类就是这n个节点分别做头节点时候的可组成的二叉搜索树的种类的和。
dp数组及下标含义 给定i个节点有dp[i]种二叉搜索树。递推公式从0到i遍历j dp[i]dp[j-1]*dp[i-j]dp数组如何初始化dp[0]1遍历顺序从小到大。打印dp数组
class Solution {
public:int numTrees(int n) {vectorint dp(n1);dp[0] 1;//初始化//递推公式for(int i 1; i n; i){for(int j 1; j i; j){dp[i] dp[j-1]*dp[i-j];//左右子树}}return dp[n];}
};class Solution {public int numTrees(int n) {int[] dp new int[n1];//dp数组初始化dp[0] 1;//迭代公式for(int i 1; i n; i){for(int j 1; j i; j){dp[i] dp[j-1]*dp[i-j];}}return dp[n];}
}class Solution(object):def numTrees(self, n)::type n: int:rtype: intdp [0]*(n1)dp[0] 1for i in range(1, n1):for j in range(1, i1):dp[i] dp[j-1]*dp[i-j]return dp[n]参考文章
https://www.programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
