动态规划之路径问题

哈喽，大家好呀，今天我给大家带来了动态规划里常见的一种问题---->路径问题，现在，让我们一起来学习吧

一.题目解析

题目如下所示

我们来看示例一，

如图，所以示例一的路径仅为2种

二.讲解算法原理

1.状态表示

我们还是使用我们一直使用的思路

创建一个二维数组dp，dp[i][j]b表示到达[i][j]一共有多少中路径

2.状态转移方程

有同学可能有这样的疑问，如果[i][j]位置没有障碍物，但[i-1][j],[i][j-1]有障碍物怎么办，我们其实不必担心，因为存在障碍物，那么到达此处的路径一定为零，加上一个零也不受影响

3.初始化

为了解决个别位置的越界问题，我们可以加上一行一列，由原来的m*n的二维数组变为（m+1)*(n+1);

然后将新加的位置进行如下初始化

这样一来，正好符合题目要求

4.填充顺序

按照由上到下，由左到右的顺序进行填充

4.返回数据

由于我们开辟的是（m+1）*(n+1)的数组，所以我们需要返回dp[i][j];

三.代码实现