动态规划——路径问题（无障碍+有障碍）_上面有若干个障碍,现在要从 (1,1) 开始,只能向右或向下走,且不能经过障碍,请问有

作者：凡人多烦事01 | 2024-04-25 08:21:32

踩

上面有若干个障碍,现在要从 (1,1) 开始,只能向右或向下走,且不能经过障碍,请问有

路径问题1（无障碍）

1、题目：力扣原题

2、问题分析：

根据题目分析，我们可以发现在网格中的任意位置(i,j)只能由其上一个状态（i,j-1）向右或者(i-1,j)向下移动得到。换句话说，当前状态存在的数目可以由上一个状态推导而来，所以可以动态规划来计算。

采用动态规划五部曲的前四部，我们可以如下分析：

1）确定dp数组及含义

dp[i][j]表示从左上角起点到位置（i,j）可以走通的路径数目；

2）确定递推公式

因为机器人只可以向右或者向左移动，所以假设某一个位置(i,j)可以由上一个状态（i,j-1）向右或者(i-1,j)向下移动得到：dp[i][j] = dp[i][j-1] + dp[i-1][j]

3)初始化

dp[i][0] = 1,因为从（0,0&#x

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/484207?site