动态规划之路径问题1

题目来源：

leetcode62：不同路径

解析题目：

从左上角到右下角的不同路径一共有多少种？只能向下或者向右

算法原理： 

状态表示：经验+题目要求

经验就是：以[i][j]位置结尾，巴拉巴拉

题目要求：以[i][j]位置结尾，一共有多少条不同的路径

状态转移方程：以最近的一步推dp[i][j]=什么

根据题目，我们不难发现，ij位置只能由[i][j-1]位置向下，或者[i-1][j]位置向右走

无论哪个方向走到[i][j]都是在原始的基础上走一步，路径不是dp[i][j-1]+1,走一步代表了还是原来的总路径，要理解清楚这一步

所以我们可以得到状态转移方程为dp[i][j]=dp[i][j-1]+dp[i-1][j];

初始化：保证填表时不会越界

不难发现我们需要用到状态转移方程最上面一行和最左边一列都会越界

第一种：也是最简单最安全最保险的一种就是把这些位置都初始化，但代码冗长

第二种：就是上一篇博客所提到的，补一行和一列，使其成为虚拟结点

要注意虚拟结点的两个注意事项：1.保证后面的填表顺序是正确的，我们不难发现最上面的一行和最左边的一列都要填1，所以我们只需要把dp[0][1]=1;这个位置设为1，然后别的位置为0，后面去填表就不会出错

2.要注意映射关系：我们原来的mXn要多开一行一列，所以填表是要注意从上面位置开始填

填表顺序：

观察发现：我们需要一行一行的填，这能保证填这个位置时有上面的也有左边的

返回值：

由于数组下标是从0开始，我们直接返回dp[m][n]即可

代码实现：

注意我们是从第一行第一列开始填表

如果不熟悉二维数组vector的使用，可以去看我们c++专栏中的STL之vector的使用