LeetCode 62 不同路径

题目描述链接：https://leetcode-cn.com/problems/unique-paths/

解题思路：笔者这里采用动态规划（当然也还有其它的多种方法能够解决此题）进行求解，即使用dp数组记忆每个的不同路径数。

（1）确定状态：采用dp[i][j]来保存移动到（i,j）网格的路径数。

（2）动态转移方程的求解：同样由于每次只能向右或向下移动，因此除了最上边和最左边的网格，其余网格只能从其上边网格或者左边网格移动过来。因此得出状态转移方程为：

dp[i][j]=dp[i-1][j]+dp[i][j-1]。

（3）确定边界问题：由于每次只能向右或向下移动，因此最上边和最左边的方案数都为1。

接下来根据分析进行编程求解即可，LeetCode参考如下：

class Solution {
public:
    
    int uniquePaths(int m, int n) {
        //动态规划求解：
        int dp[m][n];
        for(int i=0;i<m;++i){
            dp[i][0]=1;
        }
        for(int j=0;j<n;++j){
            dp[0][j]=1;
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};