1.确定状态并…今天更新动态规划路径问题1后续会继续更新其他有关动态规划的问题动态规划的路径问题顾名思义就是和路径相关的问题。

当然我们是从最简单的找路径开始

1.确定状态并定义状态数组ij代表什么意思dp[i][j]又是什么意思

2.确定状态转移方程即递推公式

不同路径方法一深度优先搜索方法二动态规划二维方法三动态规划一维方法四排列组合

二、LC

不同路径II方法一动态规划二维方法二动态规划一维方法三记忆化搜索

三、LC

机器人每次只能向下或者向右移动一步。

机器人试图达到网格的右下角在下图中标记为

“Finish”

0;//到达终点(在竖直方向达到m水平方向达到n也即坐标达到m,n))if(im

jn)

1.确定状态并定义状态数组ij代表什么意思dp[i][j]又是什么意思

2.确定状态转移方程即递推公式

dp[101][101]{0};//初始化状态数组for(int

j0;jn;j){dp[0][j]1;}//遍历for(int

i1;im;i){for(int

j1;jn;j){//状态转移dp[i][j]dp[i][j-1]dp[i-1][j];}}//返回结果return

dp[m-1][n-1];}

dp[101]{0};//初始化数组值为1即相对于二维数组第一行全是1for(int

i1;im;i){for(int

j1;jn;j){//状态转移dp[j]指的是上一行的j,dp[j-1]指的是当前行左边的j//每次状态转移都相当于先将上一行的运算拷贝过来再加上从左面来的方案数dp[j]dp[j-1]dp[j];}}return

dp[n-1];}

denominator;//约去一个公因数denominator--;}}return

numerator;}

机器人每次只能向下或者向右移动一步。

机器人试图达到网格的右下角在下图中标记为

现在考虑网格中有障碍物。

那么从左上角到右下角将会有多少条不同的路径

方法一动态规划二维

uniquePathsWithObstacles(vectorvectorint

obstacleGrid)

mobstacleGrid.size();//求出二维动态数组的列数int

nobstacleGrid[0].size();//定义状态数组int

dp[101][101]{0};//边界判断if(obstacleGrid[0][0]1

return

0;//初始化状态数组dp[0][0]1;//遍历for(int

i0;im;i){for(int

j0;jn;j){//如果是障碍物则此路不通路径数归零if(obstacleGrid[i][j]1){dp[i][j]0;continue;}//状态转移此处和上面的一样if(i0

j0)

dp[i][j]dp[i-1][j]dp[i][j-1];else

if(i0)

/*if(obstacleGrid[i][j]0){//状态转移此处和上面的一样if(i0

j0)

dp[i][j]dp[i-1][j]dp[i][j-1];else

if(i0)

uniquePathsWithObstacles(vectorvectorint

obstacleGrid)

dp(obstacleGrid[0].size(),0);//初始化一维状态数组第一行for

(int

m,n;vectorvectorintmemo;vectorpairint,intdir{{0,1},{1,0}};int

uniquePathsWithObstacles(vectorvectorint

ob)

{nob.size();mob[0].size();if(ob[0][0]1||ob[n-1][m-1]1){return

0;}memo.resize(n,vectorint(m,0));return

dfs(ob,0,0);}int

memo[i][j];}if(in-1jm-1){memo[i][j]1;return

1;}int

yjd.second;if(x0xny0ymob[x][y]0){curdfs(ob,x,y);}}memo[i][j]cur;return

memo[i][j];}

链接https://leetcode.cn/problems/unique-paths-ii/solutions/2466610/dfsji-yi-hua-sou-suo-by-gallant-murdockr-e882/

来源力扣LeetCode

dp[201][201]{0};//初始化状态数组dp[0][0]grid[0][0];//获得行数和列数int

mgrid.size();int

j0){dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j];}//边界条件else

if(i0)

dp[i][j]dp[i-1][j]grid[i][j];else

if(j0)

dp[i][j]dp[i][j-1]grid[i][j];}}return

dp[m-1][n-1];}

dp[201]{0};//初始化第一行dp[0]grid[0][0];for(int

i1;in;i){dp[i]grid[0][i]dp[i-1];}//状态转移配合滚动数组优化for(int

i1;im;i){for(int

dp[j]min(dp[j-1],dp[j])grid[i][j];}}return

dp[n-1];}

};我以前没怎么接触过动态规划目前就是每天有空看看题想想解题思路啥的但愿有效果吧