坐标型动态规划: 数组下标[i][j]就是坐标(i, j)

---

Leetcode 256 - Paint House
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

Method 1 - Rolling Array

• last state: for the last color, minimus cost = cost * miniCost while previous color is not same as current color
• dp[i][k] represents minimum cost at ith house and color is kth color
• dp[i][k] = min(dp[i - 1][j] + costs[i][j]) while j != k
• dp[0][k] = costs[0][k]

    // Time Complexity: N
    // Space Complexity: N
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        
        int[][] dp = new int[2][3];
        int old = 0;
        int now = 1;
        
        for (int i = 0; i < costs.length; i++) {
            now = old;
            old = 1 - now;
            
            for (int j = 0; j < 3; j++) {
                if (i == 0) {
                    dp[now][j] = costs[i][j];
                    continue;
                }    
                
                dp[now][j] = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (k != j) {
                        dp[now][j] = Math.min(dp[now][j], dp[old][k] + costs[i][j]);    
                    }    
                }
            }    
        }
        
        return Math.min(dp[now][0], Math.min(dp[now][1], dp[now][2])); 
    }

Method 2: since there are only 3 color, so update previous house, using temp variable to keep first and second house costs

    // Time Complexity: N
    // Space Complexity: N
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        
        int[] dp = new int[3];
        
        for (int i = 0; i < costs.length; i++) {
            int tempZero = dp[0];      
            dp[0] = Math.min(dp[1], dp[2]) + costs[i][0]; 
            
            int tempOne = dp[1];
            dp[1] = Math.min(tempZero, dp[2]) + costs[i][1];
            
            dp[2] = Math.min(tempZero, tempOne) + costs[i][2];
        }
        
        return Math.min(dp[0], Math.min(dp[1], dp[2])); 
    }

Summary

1. 序列型动态规划: ...**前i个** ...最小/方式数目/可行性
2. 在设计动态规划的过程中, 发现需要知道油漆前N - 1栋房子的最优策略中， 房子N - 2的颜色
3. 如果只用dp[N - 1],将无法区分
4. 解决方式:  记录房子N - 2的颜色， 在房子N-2是 红/蓝/绿的情况下，油漆前N-1栋房子的最小花费

Overal, 就是序列 + 状态

---

Leetcode 91 - Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6)

Analysing the question

• Last state: there must be a last letter, this letter coulbe be 1 ~ 26
• So we need to know number of decoding ways for the first n - 1 letters and first n - 2 letters
• Subproblems: let's say dp[i] represents number of decoding ways for the first i letters
• Transfer state equation:
  • dp[i] = dp[i - 1] + dp[i - 2]
  • dp[0] = 1 meaning empty string has one way to decode
• terminate condition: if i = 1, only care about last number
• calculation sequence, dp[0], dp[1], dp[2], ..., dp[N]
• return dp[N]
• Time Complexity: N
• Space Complexity: N

    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 1;
        }    
        
        int length = s.length();
        int[] dp = new int[length + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= length; i++) {
            int currNum = s.charAt(i - 1) - '0';                            
            
            if (i == 1) {
                if (currNum > 0) {
                    dp[i] = 1;
                } 
                
                continue;
            }
            
            if (currNum > 0) {
                dp[i] += dp[i - 1];
            }
            
            int num = (s.charAt(i - 2) - '0') * 10 + currNum;
            if (num > 9 && num <= 26) {
                dp[i] += dp[i - 2];         
            }
        }
        
        return dp[length];
    }

坐标型动态规划总结

1. 给定一个序列或者网格

2. 需要找到序列中某个/些子序列或网格中的某条路径
    - 某种性质最大/最小
    - 计数
    - 存在性

3. 动态规划方程f[i]中下标i表示以ai为结尾的满足条件的子序列的性质, f[i][j]中的下标i,j表示以格子(i,j)为结尾的满足条件的路径的性质.
     - 最大值/最小值
    - 个数
    - 是否存在

4.  坐标型动态规划的初始条件f[0]就是指以a0为结尾的子序列的性质

---

Leetcode 674 Longest Continuous Increasing Subsequence
Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Analysing the problem

• Last state: For the bottom right element, based on the best solution, it must have a path from top or right
• So we need to need minimum path sum from 0,0 to top and right
• Subproblems: let's say dp[i][j] represents minimum path sum from (0,0) to (i,j)
• Transfer state euqation:

  •  dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]) if i > 0 or j > 0
    

  •  initial state: dp[0][0] = grid[0][0]
    

• Termination Condition:

  •  dp[i][j] = grid[i][j] if i = 0 && j =0
    

  •  dp[i][j] = dp[i][j - 1] + grid[i][j] if i = 0 
    

  •  dp[i][j] = dp[i - 1][j] + grid[i][j] if j = 0
    

• return dp[m - 1][n - 1]
• Time Complexity: m * n
• Space Complexity: m * n

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }    
        
        int rows = grid.length;
        int cols = grid[0].length;
        
        int[][] dp = new int[2][cols];
        int old = 0;
        int now = 1;
        
        for (int i = 0; i < rows; i++) {
            old = now;
            now = 1 - old;
            
            for (int j = 0; j < cols; j++) {
                if (i == 0 && j == 0) {
                    dp[now][j] = grid[i][j];
                    continue;
                }
                
                if (i == 0) {
                    dp[now][j] = dp[now][j - 1] + grid[i][j]; 
                    continue;
                }
                
                if (j == 0) {
                    dp[now][j] = dp[old][j] + grid[i][j];
                    continue;
                }
                
                dp[now][j] = Math.min(dp[now][j - 1], dp[old][j]) + grid[i][j];
            }
        } 
        
        return dp[now][cols - 1];
    }

空间优化Summary

1. 对于网络上的动态规划， 如果f[i][j]只依赖本行的f[i][x]与前一行的f[i - 1][j]， 
那么就可以采用滚动数组的方法压缩空间。空间复杂度O(N).

2. 如果网格行数少列数多(大胖子网格)， 那么就可以逐列计算，滚动数组的长度为行数，
空间复杂度O(M).

几乎可以用这样的模板去解决:
    int old = 0;
    int now = 1;
    
    for (int i = 0; i < rows; i++) {
        old = now;
        now = 1 - old;
      
        for (int j = 0; j < cols; j++) {
            # for starting point
            if (i == 0 && j == 0) {
                # do something;
                dp[now][j] = something;
                continue;
            }

            # for the first row
            if (i == 0) {
                dp[now][j] = something;
                continue;
            }
            
            # for the first column
            if (j == 0) {
                dp[now][j] = something;
                continue;
            }

            # otherwise do something
            dp[now[j] = dp[old][j] + dp[now][j - 1];
        }
    }

---

Leetcode 361 - Bomb Enemy
Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note: You can only put the bomb at an empty cell.

Example:

Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3
Explanation: For the given grid,

0 E 0 0
E 0 W E
0 E 0 0

Placing a bomb at (1,1) kills 3 enemies.

• Figure out the state

  •  1. In enemy cell, enemy will be dead, then keep exploring in up direction
    

  •  2. In wall cell, no enemy dead
    

• Plant a bomb in grid[i][j], the number of dead enemy in up direction will be:

  •  1. grid[i][j] is enmpty -> number of dead enemy in (i - 1, j)
    

  •  2. grid[i][j] is enemy -> number of dead enemy in (i - 1, j) + 1
    

  •  3. grid[i][j] is wall -> 0 
    

• So we need to know in (i - 1, j), if we plant a bomb, how many enemy will be dead
• Subproblem:
• State transfer equation: let's say up[i][j] represents number of dead enemy in up direction if we plant a bomb in (i, j)

  •  up[i][j] = up[i - 1][j] if grid[i][j] is empty   
    

  •  up[i][j] = up[i - 1][j] if grid[i][j] is enemy
    

  •  up[i][j] = 0 if grid[i][j] is wall
    

  •  initial state: up[0][j] = 0 if not enemy, otherwise 1 
    

• Calculation sequence: up[0][0] ..... up[0][n - 1], up[1][0] ... up[1][n - 1], ... up[m][0] ... up[m][n - 1]
• Time Complexity: M * N
• Space Complexity: M * N
• Similarly, get the other three directions, left[i][j], right[i][j], down[i][j]

    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }    
        
        int rows = grid.length;
        int cols = grid[0].length;
        
        int[][] up = new int[rows][cols];
        int[][] left = new int[rows][cols];
        int[][] right = new int[rows][cols];
        int[][] down = new int[rows][cols];
        
        // up
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == 0) {
                    up[i][j] = grid[i][j] == 'E' ? 1 : 0; 
                } else {
                    if (grid[i][j] == '0') {
                        up[i][j] = up[i - 1][j];
                    } else if (grid[i][j] == 'E') {
                        up[i][j] = up[i - 1][j] + 1; 
                    } else {
                        up[i][j] = 0;
                    }     
                }    
            }
        }
        
        // left
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (j == 0) {
                    left[i][j] = grid[i][j] == 'E' ? 1 : 0; 
                } else {
                    if (grid[i][j] == '0') {
                        left[i][j] = left[i][j - 1]; 
                    } else if (grid[i][j] == 'E') {
                        left[i][j] = left[i][j - 1] + 1;
                    } else {
                        left[i][j] = 0;
                    }
                }    
            }
        }        
        
        // down 
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (i == rows - 1) {
                    down[i][j] = grid[i][j] == 'E' ? 1 : 0;
                } else {
                    if (grid[i][j] == '0') {
                        down[i][j] = down[i + 1][j];    
                    } else if (grid[i][j] == 'E') {
                        down[i][j] = down[i + 1][j] + 1;
                    } else {
                        down[i][j] = 0;
                    }
                }        
            }
        }
        
        // right
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (j == cols - 1) {
                    right[i][j] = grid[i][j] == 'E' ? 1 : 0;
                } else {
                    if (grid[i][j] == '0') {
                        right[i][j] = right[i][j + 1];
                    } else if (grid[i][j] == 'E') {
                        right[i][j] = right[i][j + 1] + 1;    
                    } else {
                        right[i][j] = 0;
                    }
                }     
            }
        }        
        
        int maxNum = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int numOfDead = 0; 
                if (grid[i][j] == '0') {
                    numOfDead = up[i][j] + left[i][j] + right[i][j] + down[i][j];    
                }
                
                maxNum = Math.max(maxNum, numOfDead);    
            }
        }
        
        return maxNum;
    }

坐标型动态规划总结

1. 给定输入为序列或者网格/矩阵

2. 动态规划状态下标为序列下标i或者网格坐标(i, j)
    - f[i]: 以第i个元素结尾的某种性质
    - f[i][j]: 到格子(i,j)的路径的性质

3. 初始化设置f[0]的值/f[0][0 .. n-1]的值

4. 二维空间优化: 如果f[i][j]的值只依赖当前和前一行，则可以用滚动数组节省空间.

---

Leetcode 338 - Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2
Output: [0,1,1]
Example 2:

Input: 5
Output: [0,1,1,2,1,2]
Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

• State: Observe a number in binary format

  •  - (170)10 = (10101010)2
    

• For the last step: Observe last bit, get rid of it, to see the number of '1' in it

  •  - (170)10 = (10101010)2
    

  •  - (85)10 = (1010101)2
    

  •  - 85 has 4 '1' in binary representation
    

  •  - then 170 has 4 '1'
    

• So we want to get number of '1' in N, we need to know number of '1' in Y, where Y = (N >> 1)
• Subproblem: let's say f[i] represents number of '1'
• State transfer equation: f[i] = f[i >> 1] + (i & 1)
• Initial state and terminate condition: f[0] = 0
• Calculation sequence: f[0], f[1], f[2], ..., f[N]
• Time Complexity: N
• Space Complexity: N

    public int[] countBits(int num) {
        if (num == 0) {
            return new int[1];
        }        
        
        int[] result = new int[num + 1];
        result[0] = 0;
        result[1] = 1;
        
        for (int i = 2; i <= num; i++) {
            result[i] = result[i >> 1] + (i & 1);
        }
        
        return result;
    }