新网站如何做快照,电子营业执照,企业网站建设总结报告,网站设计成手机Day39 动态规划第二天
LeetCode 62.不同路径
二维dp数组的含义#xff1a;走到位置为(i,j)的格子的走法为dp[i][j]种。 递推公式#xff1a;dp[i][j]dp[i-1][j]dp[i][j-1]。 初始化#xff1a;dp[i][0]和dp[0][j]都赋值为1. 递归顺序#xff1a;从左往右#xff0c;从上…Day39 动态规划第二天
LeetCode 62.不同路径
二维dp数组的含义走到位置为(i,j)的格子的走法为dp[i][j]种。 递推公式dp[i][j]dp[i-1][j]dp[i][j-1]。 初始化dp[i][0]和dp[0][j]都赋值为1. 递归顺序从左往右从上到下。
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m,vectorint(n,0));for(int i0;im;i) dp[i][0]1;for(int j0;jn;j) dp[0][j]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];}
};LeetCode 63.不同路径II
二维dp数组的含义走到位置为(i,j)的格子的走法为dp[i][j]种. 递推公式没有障碍即obs[i][j]0时dp[i][j]dp[i-1][j]dp[i][j-1]。 ※初始化没遇到障碍时dp[i][0]和dp[0][j]都赋值为1遇到障碍后后面全是0. 遍历顺序从左往右从上到下。
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int mobstacleGrid.size(),nobstacleGrid[0].size();vectorvectorint dp(m,vectorint(n,0));if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1) return 0;for(int i0;im obstacleGrid[i][0]0;i) dp[i][0]1;for(int j0;jn obstacleGrid[0][j]0;j) dp[0][j]1;for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]0)dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
};动态规划有点感觉了。
