题解 | #求路径#

这个题的思路通过画图列一下就可以找到思路。
我们把走到某个点有多少种路径，作为该点的值填到图中。
首先是只有行和只有列的两种情况，那么这样的情况下就只有一种路径。
m行1列，那么这一列上的任意一个点，作为终点，都只有一种路径

同理1行n列，那么这一行上的任意一个点，作为终点，都只有一种路径

接下来讨论m行n列的情况，以题目中的4行5列为例。
首先拆分成单点来看，不直接看到终点，而是从起点一步步来。
那么为了方便描，先对题目中的图中的各个格子进行编号如下。

那么从起点00到01，可以知道只有1种走法；00到10，1种走法；那么00到11的走法只有2种，这两种是怎么来的呢，可以这样看：因为只能从起点向右或向下走，所以从终点的角度来看，上一步就只能是该位置的上面或者左面，也就是到该位置的方法数=到该位置上面的方法数+到该位置左边的方法数；而分别到该位置上面或左面的方法数在之前的过程中是求出来了的，所以是利用了迭代的思想。归结成公式，假设dp[i][j]表示起点到第i行第j列的位置的路径数，那么dp[i][j]=dp[i-1][j]+dp[i][j-1]即可。
具体的实现过程可参考下面的动图。

代码如下

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        int dp[100][100];
        for(int i=0;i<n;i++)
        {
            dp[0][i]=1;//第一行初始化为1
        }
        for(int i=0;i<m;i++)
        {
            dp[i][0]=1;//第一列初始化为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];
    }
};