leetcode 不同路径

这个题目很容易想到用 dp 来做，而且状态转移方程也很简单，

标准方程是 ：dp[i][j] = dp[i-1][j] + dp[i][j-1].

我的方程：dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i][j]。 多加了一个。因为我预处理的时候，把所有带 0 的部分都处理成了 0，然后dp[1][1] 设置的为1.

这样其实并不好用。

更好的方法，if(j ==0 || j == 0) dp[i][j] = 1;

复杂度为 N*2

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m+1][n+1];
        for(int i = 0; i < m + 1; i++){
            dp[i][0] = 0;
        }
        for(int i = 0; i < n + 1; i++){
            dp[0][i] = 0;
        }
        dp[1][1] = 1;
        for(int i = 1; i < m+1; i++)
            for(int j = 1; j < n+1; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i][j];
            }
        return dp[m][n];
    }
}