[数据结构与算法]leetcode 576.出界的路径数（动态规划路径问题详解）

读完题目的第一想法是利用递归，在设置一个方向数组后，进行递归，但觉得递归必然时间不够，果不其然，超出时间限制。

后来用动态规划的方法进行操作感觉能解决这个问题。

（动态规划是一个格外存储空间的循环，再次说一遍！！！）

状态定义

题目提供了主要的三个参数，最大移动步数MaxMove，开始的坐标行和列StartRow和StartCloumn。

定义dp[k][i][j]为第k次移动，从起点到（i,j）坐标的路径数量。

?

转移方程

在第k次移动未出界情况下，分析第k+1次，有两种情况：

1.第k+1次移动并未出界，(i'，j')是（i，j）的一个邻近点，根据定义，(i'，j')中必然包含（i，j）的路径。

????????dp[k+1][i'][j']=dp[k+1][i'][j']+dp[k][i][j]。i' 为 i 变换得到，j' 为 i 变换得到。

? ??

2.若第k+1次出界，dp[k][i][j]必然加入路径数量的总数中。

初始状态

dp[0][StartCloumn][StartRow]=1;其余为0；

最后结果

result;?

总结

dp的计算是前后两个的计算，可以将dp的维度降维为二维，利用两个二维的数组。