力扣62-不同路径（C++，留个思路）

 

思路：

动态规划类似于递归，就是发现大问题可以用小问题来做。

1.确定用动态规划

这个题怎么发现是动态规划的呢？首先想到0，1和1，0和1，1这三个位置，这三个位置最好看，前两个都是只走一步，1，1发现得从1，0或0，1过来，所以是1+1=2条路，再往下想别的位置，又是从1，1过来的了。

所以发现无论多远好像都是从起点开始的，所谓万丈高楼平地起这个感觉，想求远处的，就得先去求近处的，就想到动态规划了。

2.动态规划dp数组是什么，怎么界定递推公式

题里问的是走到坐标是x，y的位置有几条路，所以dp数组也来一个二维的，dp[x][y]就是从0，0走到x，y有几条路。

递推公式刚才三个坐标就可以确定了，除了0，y和x，0这样的只有一条路，其他就是dp[x][y] = dp[x-1][y] + dp[x][y-1]了，因为只能向下或者向右走，所以只有两个方向可以过来。

3.怎么初始化

0，y和x，0这样的只有一条路，就是一直走一个方向的直达，所以可以初始化为1；其他的都不能一开始就算出来，所以只能初始化这两个方向的。

至于0，0就初始化为0，因为不用走就到了。

代码截一个Carl哥的，思路就是照着评论区他的题解写的。