[62] Unique Paths

腦袋裝漿糊.........
完全不會DP的精神了 囧
給一個m跟n 象徵 m x n 的棋盤格
若起始點在最左上角(比方說0,0)
只能向右或是向下走,
問走到最右下角(比方說m,n)的走法共有幾種不同走法
注意之一是m,n 是從1開始,
和C的array從0 開始不同;
注意之二就是......
應該要存前一個round算出來的步數啊啊啊
雖然我知道但是怎麼一直想到費伯那器,
然後就在那邊 steps(m-1, n) + steps(m, n-1)
遞迴到天荒地老啊啊啊啊啊
到底我有沒有搞懂DP呢感覺沒有啊XD~

Unique Paths
int uniquePaths(int m, int n) {
    int *res = malloc(sizeof(int)*n);
    int i,j;
    for(j=0;j<n;j++)
        res[j]=1;

    for(i=1;i<m; i++)
        for(j=1;j<n;j++)
            res[j] = res[j-1] + res[j];
    return res[n-1];  
}