LeetCode上的经典动态规划问题

63. 不同路径II

class Solution {
    public int uniquePathsWithObstacles(int[][] nums) {
        if (nums == null)
            return 0;
        int n = nums.length; int m = nums[0].length;
        int[][] state = new int[n][m];
        state[0][0] = 1 - nums[0][0];
        for (int i =0; i< n; i++){
            for (int j = 0; j < m; j++){
                if (i == 0 && j == 0)
                    continue;
                if (nums[i][j] == 1)
                    state[i][j] = 0;
                else{
                    if (i >0)
                        state[i][j] += state[i - 1][j];
                    if (j >0)
                        state[i][j] += state[i][j - 1];
                }
            }
        }
        
        return state[n - 1][m - 1];
    }
}

	

62. 不同路径

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