系統設計看一段落了，先休息一下，回到刷題loop。
發現自己對dp推倒算式實在很薄落...多練習多練習O_Q
來篩選出一些有dp的題目來做做
key: 先推導算式 以及轉移方程 再進行coding

Regular Expression Matching

Q: https://leetcode.com/problems/regular-expression-matching/description/

class Solution {
    public boolean isMatch(String text, String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--){
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean first_match = (i < text.length() &&
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

Unique Paths II

Q: https://leetcode.com/problems/unique-paths-ii/description/

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] memo = new int[n][m];
        memo[0][0] = 1;
        int[] location = new int[] {0, 0};
        Queue<int[]> q = new LinkedList<>();
        q.offer(location);
        int[][] directions = new int[][] {{1,0}, {0, 1}};
        while(!q.isEmpty()) {
            int[] now = q.poll();
            for (int[] direction : directions) {
                int newRow = now[0] + direction[0];
                int newCol = now[1] + direction[1];
                if (newRow >= 0 && newRow < n && newCol >= 0 
                        && newCol < m && obstacleGrid[newRow][newCol] != 1
                        && memo[newRow][newCol] == 0) {
                    if (newRow == 0) {
                        memo[newRow][newCol] = memo[newRow][newCol - 1];
                    } else if (newCol == 0) {
                        memo[newRow][newCol] = memo[newRow - 1][newCol];
                    } else {
                        memo[newRow][newCol] = memo[newRow - 1][newCol] + memo[newRow][newCol - 1];
                    }
                    q.offer(new int[]{newRow, newCol});
                }
            }
        }
        return memo[n-1][m-1];
    }
}

Minimum Path Sum

Q: https://leetcode.com/problems/minimum-path-sum/description/

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