leadcode的Hot100系列--62. 不同路径--简单的动态规划

题目比较清晰，简单来说就是：

a	b	c	d
e	f	g	h
i	j	k	l

只能往右或者往下，从a到l，能有几种走法。
这里使用动态规划的方法来做一下。
动态规划最重要的就是动态方程，这里简单说下这个动态方程怎么做出来的吧。

---

记 f(b) 为 a到b总共可以有的走法。
想知道f(l)，那其实只要知道f(h)和f(k)就可以了。
因为从a到h之后，再想到l就只有一种方法，ak同理，所以 f(l) = f(h) + f(k)。

那f(h)呢，就等于 f(d)+f(g)，这里就很容易得到他的动态方程：

f [i] [j] = f [i] [j-1] + f [i-1] [j] // i 代表行，j 代表列

得到状态方程之后，最后再考虑一下边界的情况，也就是 f(a) f(b) f(e) f(i) 等。
因为题目已经规定了，只能往右走，或者往下走，
所以第一行的走法都是只有1，第一列的走法也是只有1，可以得到：

1	1	1	1
1	f(f)	f(g)	f(h)
1	f(j)	f(k)	f( l)

so：f(f) = f(b) + f(e) = 1 + 1 = 2
f(g) = f(c) + f(f) = 1 + 2 = 3
f(h) = f(d) + f(g) = 1 + 3 = 4
f(j) = f(i) + f(f) = 1 + 2 = 3
f(k) = f(g) + f(j) = 3 + 3 = 6
f(l) = f(h) + f(k) = 4 + 6 = 10

这里附上代码：

int uniquepaths(int m, int n){
    int dp[100][100]={0}, i, j;
    for (i=0; i<m; i++)     // 这里初始化第一列的走法为1
        dp[i][0] = 1;
    for (i=0; i<n; i++)   // 这里初始化第一行的走法为1
        dp[0][i] = 1;
    
    for (i=1; i<m; i++)
    {
        for (j=1; j<n; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];   // 动态方程
        }
    }
    
    return dp[m-1][n-1];
    
}