北京网站制作合肥,如何看网站空间问题,网站创建的流程是什么,seo网站关键词排名快速1、不同路径II#xff08;难度中等#xff09; 该题对应力扣网址
AC代码
只会写简单的if-else
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {//1、定义子问题//2、子问题递推关系//3、确定dp数组的计算顺序…1、不同路径II难度中等 该题对应力扣网址
AC代码
只会写简单的if-else
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {//1、定义子问题//2、子问题递推关系//3、确定dp数组的计算顺序int mobstacleGrid.size();int nobstacleGrid[0].size();vector vectorint dp(m,vectorint(n));dp[0][0]1;if(m1 n1 obstacleGrid[m-1][n-1]0) return 1;if(m1 n1 obstacleGrid[m-1][n-1]1) return 0;if(obstacleGrid[m-1][n-1]1){return 0;}for(int i0;im;i){for(int j0;jn;j){if(i0 j0){dp[i][j]1;}if(i0 j!0){if(obstacleGrid[i][j-1]1){dp[i][j]0;}else{dp[i][j]dp[i][j-1];}}if(j0 i!0){if(obstacleGrid[i-1][j]1){dp[i][j]0;}else{dp[i][j]dp[i-1][j];}}if(i!0 j!0){if(obstacleGrid[i-1][j]1 obstacleGrid[i][j-1]1){dp[i][j]0;}if(obstacleGrid[i-1][j]1 obstacleGrid[i][j-1]0){dp[i][j]dp[i][j-1];}if(obstacleGrid[i][j-1]1 obstacleGrid[i-1][j]0){dp[i][j]dp[i-1][j];}if(obstacleGrid[i][j-1]0 obstacleGrid[i-1][j]0){dp[i][j]dp[i-1][j]dp[i][j-1];}}}}return dp[m-1][n-1];}
};2、三角形最小路径和难度中等 该题对应力扣网站
AC代码
主要思路
要知道这是个三角形
分为三种情况
1、最后一行的最左边(j0)这时候j-1超出范围dp[i][j]dp[i-1][j]triangle[i][j];
2、最后一行的最右边(ji)这时候j超出范围dp[i][j]dp[i-1][j-1]triangle[i][j];
3、剩余情况dp[i][j]min(dp[i-1][j]triangle[i][j],dp[i-1][j-1]triangle[i][j]);最后遍历最后一行返回最小值class Solution {
public:int minimumTotal(vectorvectorint triangle) {int mtriangle.size();int ntriangle[m-1].size();vector vectorint dp(m1,vectorint(n1));dp[0][0]triangle[0][0];if(m0)return triangle[0][0];for(int i1;im;i){for(int j0;ji1;j){if(j0){dp[i][j]dp[i-1][j]triangle[i][j];}if(ji){dp[i][j]dp[i-1][j-1]triangle[i][j];}if(j!i j!0){dp[i][j]min(dp[i-1][j]triangle[i][j],dp[i-1][j-1]triangle[i][j]);}}}int minINT_MAX;for(int k0;kn;k){if(dp[m-1][k]min){mindp[m-1][k];}}return min;}
};
