leadcode的Hot100系列--62. 不同路徑--簡單的動態規劃

題目比較清晰，簡單來說就是：

只能往右或者往下，從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，可以得到：

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];
    
}