Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?

难度：medium

Solution: Dynamic Programming

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

Unique Paths II

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid.

难度：medium

Solution: Dynamic Programming

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] pathes = new int[m][n];
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(obstacleGrid[i][j] == 1) {
                    pathes[i][j] = 0;
                    continue;
                }
                if(i == 0) {
                    pathes[i][j] = j == 0 ? 1 : pathes[i][j - 1];
                }
                if(j == 0) {
                    pathes[i][j] = i == 0 ? 1 : pathes[i - 1][j];
                }
                if(i != 0 && j != 0) {
                    pathes[i][j] = pathes[i][j - 1] + pathes[i - 1][j];
                }
            }
        }
        return pathes[m - 1][n - 1];
    }
}

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.

难度：medium

Solution: Dynamic Programming

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] pathSum = new int[m][n];
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i == 0) {
                    pathSum[i][j] = j == 0 ? grid[i][j] : grid[i][j] + pathSum[i][j - 1];
                }
                if(j == 0) {
                    pathSum[i][j] = i == 0 ? grid[i][j] : grid[i][j] + pathSum[i - 1][j];
                }
                if(i != 0 && j != 0) {
                    pathSum[i][j] = Math.min(pathSum[i - 1][j], pathSum[i][j - 1]) + grid[i][j];
                }
            }
        }
        return pathSum[m - 1][n - 1];
    }
}

Dungeon Game

Hard

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. Notes: The knight's health has no upper bound. Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Solution: Dynamic Programming

This is first problem that the target value is on the left-up corner instead of right-down corner. So we need to start from right-down towards left-up.

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

        int dp[][] = new int[m][n];
        dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);
        for(int i = m - 2; i >= 0; --i) {
            dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for(int j = n - 2; j >= 0; --j) {
            dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }

        for(int i = m - 2; i >= 0; --i) {
            for(int j = n - 2; j >= 0; --j) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }

        return dp[0][0];
    }
}