东莞网站制作网站推广价钱,电子商务网站建设作文,双语对照网站,汕头网站制作找哪里63. 不同路径 II 思路#xff1a;
动态规划 dp[i][j] #xff1a;表示从#xff08;0 #xff0c;0#xff09;出发#xff0c;到(i, j) 有dp[i][j]条不同的路径 根据题意#xff0c;只能向下或者向右移动一步#xff0c;则dp[i][j] dp[i - 1][j] dp[i][j - 1] 但是…63. 不同路径 II 思路
动态规划 dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径 根据题意只能向下或者向右移动一步则dp[i][j] dp[i - 1][j] dp[i][j - 1] 但是如果(i, j) 处有障碍则dp[i][j] 0 最后求得dp[n-1][m-1]即为从左上角到右下角路径数 注意在对dp数组进行初始化时如果遇到了障碍那么在障碍位置上及之后位置上的dp值都应该为0
代码
#includestdio.h
#includevector
#includestring.h
#includestring
#includealgorithm
using namespace std;class Solution
{
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid){int dp[105][105];memset(dp,0,sizeof(dp));// 行数int nobstacleGrid.size();// 列数int mobstacleGrid[0].size();for(int i0; in; i)if(obstacleGrid[i][0]!1)dp[i][0]1;elsebreak;for(int j0; jm; j)if(obstacleGrid[0][j]!1)dp[0][j]1;elsebreak;for(int i1; in; i)for(int j1; jm; j)if(obstacleGrid[i][j]!1)dp[i][j]dp[i-1][j]dp[i][j-1];return dp[n-1][m-1];}
};int main()
{vectorvectorint num{{1,0},{0,0}};Solution *solutionnew Solution();int anssolution-uniquePathsWithObstacles(num);printf(%d\n,ans);delete(solution);return 0;
} 总结刚开始写这道题时在对dp数组进行初始化时没有考虑到障碍之后就没路了...在此记录
