当前位置：首页 > news >正文

【动态规划】1、不同路径II+2、三角形最小路径和

news 来源：原创 2024/9/20 9:41:36

1、不同路径II（难度中等）

在这里插入图片描述

该题对应力扣网址

AC代码

只会写简单的if-else

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {//1、定义子问题//2、子问题递推关系//3、确定dp数组的计算顺序int m=obstacleGrid.size();int n=obstacleGrid[0].size();vector <vector<int>> dp(m,vector<int>(n));dp[0][0]=1;if(m==1 && n==1 && obstacleGrid[m-1][n-1]==0) return 1;if(m==1 && n==1 && obstacleGrid[m-1][n-1]==1) return 0;if(obstacleGrid[m-1][n-1]==1){return 0;}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(i==0 && j==0){dp[i][j]=1;}if(i==0 && j!=0){if(obstacleGrid[i][j-1]==1){dp[i][j]=0;}else{dp[i][j]=dp[i][j-1];}}if(j==0 && 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、最后一行的最左边(j==0)：这时候j-1超出范围dp[i][j]=dp[i-1][j]+triangle[i][j];
2、最后一行的最右边(j==i)：这时候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(vector<vector<int>>& triangle) {int m=triangle.size();int n=triangle[m-1].size();vector <vector<int>> dp(m+1,vector<int>(n+1));dp[0][0]=triangle[0][0];if(m==0)return triangle[0][0];for(int i=1;i<m;i++){for(int j=0;j<i+1;j++){if(j==0){dp[i][j]=dp[i-1][j]+triangle[i][j];}if(j==i){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 min=INT_MAX;for(int k=0;k<n;k++){if(dp[m-1][k]<min){min=dp[m-1][k];}}return min;}
};