62 Unique Paths

很明显的dp，M x N的矩阵每个位置的unique paths数取决于上和左的path数

初始化0，0为一，边界没有上或者右。

class Solution {
    public int uniquePaths(int m, int n) {
        int [][] dp = new int [m][n];
        dp[0][0]=1;
        //go down:i++ go right j++;
        //for up i-1 for left j-1;
        for (int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if (i==0&&j==0) continue;
                if(i==0) {dp[i][j]=dp[i][j-1];}
                else if(j==0){dp[i][j]=dp[i-1][j];}
                else {dp[i][j]=dp[i][j-1]+dp[i-1][j];}
            }
        }
        return dp[m-1][n-1];
    }
}

应该是可以不建一个两维的dp直接就是长度为n的dp就够了，改天试试

Follow Up

63 Unique Paths 2

有障碍物的path，输入障碍物数组，就直接在上面做dp了，就像120的Triangle那样

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if (obstacleGrid[i][j]==1) obstacleGrid[i][j]=0;
                else if (i==0&&j==0) obstacleGrid[i][j]=1;
                else if (i==0)obstacleGrid[i][j]=obstacleGrid[i][j-1];
                else if (j==0)obstacleGrid[i][j]=obstacleGrid[i-1][j];
                else obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];

            }
        }
        return obstacleGrid[m-1][n-1];

    }
}