动态规划之路径问题_规划路径问题

作者：码创造者 | 2024-08-07 05:53:33

踩

规划路径问题

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

一.题目解析

题目如下所示

我们来看示例一，

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

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

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

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

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

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

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

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

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

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