初识动态规划，我对这个算法的理解是这样的：
1.找到初始值-原始解
2.在找到各种解与原始解的关系
3.通过循环得到答案
适用于动态规划的问题首先就是不同路径：
问题是给定一个M*N的地图从左上到右下角一共有多少种不同的方案（每次只能向右或者向下走一格）。
那么解决这个问题的关键在于你如何确定初始解与答案之间的联系。
首先我们可以确定地图的左边与上边都为1，因为只能往右或者下走。
例如从【0，0】走到【0，5】只能选择连续向右走五步，或者从【0，0】走到【5，0】只能选择连续向下走五步。
那么走到【1，1】有多少种走法？ 根据每次只能向下走一步或者向右走一步的特性，所以只能由【0，1】或者【1，0】到达【1，1】。也就是说【1，1】的走法就是【1，0】的走法加上【0，1】的走法。
其他类似，只需要知道左边与上面的格子的走法也就知道本格子的走法了。
这时我们设置一个二维数组DP【】【】，表示从【0，0】到【i，j】之间有多少种走法。
那么结合之前的分析可以得知DP【i】【j】 = DP【i – 1】【j】 + DP【i】【j – 1】
代码如下：
Original: https://www.cnblogs.com/Yeqqsy/p/16405712.html
Author: Yeqsy
Title: leetcode 不同路径
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604515/
转载文章受原作者版权保护。转载请注明原作者出处！