算法小结 -- Dynamic Programming解法

DP
就是每次运算的结果是建立在上一次运算结果的基础之上
在while/for loop里面解决sub problem（和original problem建立联系）

Time Complexity:  O(cⁿ)  T(n) = T(n-1) + T(n-2) which is exponential.

T(n)=T(n-1)+T(n-2)+ .... +T(1)+T(0)

assume T(0)=1, T(1)=1

T(2)=T(1)+T(0)=2
T(3)=T(2)+T(1)+T(0)=2+2=4
.....
T(n)=2^n

做法： https://www.interviewcake.com/concept/java/bottom-up
a.Top-Down( recursion) - start from end and work backwards, O(n) stack space cost

b.bottom up(memoization) - start from begin, dp[] array to keep a record for given inputs

套路代码, 一般define一个dp[] array存当前相关index的结果，总体loop array，return dp[n]（或其他）

public class Solution {//53. Maximum subarray
    public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];有时候[n+1]
        dp[0] = A[0];
        int max = dp[0];//max sum of arr[0..i]
        for(int i = 1; i < n; i++){
            dp[i] = A[i]+ (dp[i-1]>0?dp[i-1]:0);//in subproblem, A[i] must be contained in max value of current subarray with A[i]
            max = Math.max(max,dp[i]);//max to track the maximum of each max of current subarray A[i]
        }
        return max;
    }
}

➤单array操作， 根据上一次的运算，来fill 一个array, return the last element of array
» 263.264 Ugly Number(Recur) + II(DP) 
http://rainykat.blogspot.com/2017/01/leetcpde-263264-ugly-numberrecur-iidp.html 
» 300. Longest Increasing Subsequence 微软
 http://rainykat.blogspot.com/2017/01/leetcode-300-longest-increasing.html
» 53. Maximum subarray LinkedIn 微软
http://rainykat.blogspot.com/2016/12/leetcodelinkedin-maximum-subarraydp-or.html 
» 139. Word Break 各大家
http://rainykat.blogspot.com/2016/12/leetcode-word-breakdp.html
» 38.  Count and Say F家
http://rainykat.blogspot.com/2017/01/leetcodef-count-and-saydp.html 
» 70. Climbing Stair Adobe Apple
分析问题，发现每次应该得到的结果就是Fibonacci number
http://rainykat.blogspot.com/2016/12/leetcode-climbing-stairs-fibonacci-dp.html
 » 279.Perfect Squares G家
将array fill Integer.MAX_VALUE（不能为空）prefill value to be replaced
http://rainykat.blogspot.com/2016/12/leetcode-perfect-squaresdp.html
» 338. Counting Bits 
http://rainykat.blogspot.com/2017/01/leetcode-338-counting-bitsdp.html
» 377. Combination Sum IV 各大家
looks like double loop, but we still fill dp[] one time.
It just need to iterate through nums to compute one dp[i]
http://rainykat.blogspot.com/2017/02/leetcode-377-combination-sum-ivdp.html 
» 91. Decode Ways F家微软Uber
http://rainykat.blogspot.com/2017/01/leetcodef-91-decode-waysdp.html
» 322. Coin Change

http://rainykat.blogspot.com/2017/04/leetcode-322-coin-changedp.html


➤dp[m+1][n+1]//matrix

int m = a.length, n = a[0].length;
int[][] dp = new int[m+1][n+1];//pre fill exterior array for calc dp[i][j]

» 221. Maximal Square 各大家
http://rainykat.blogspot.com/2017/01/leetcode-221-maximal-squaredp.html
» 10. Regular Expression Matching 各大家
tick - mark dp[0][0] true for prefilled default value
http://rainykat.blogspot.com/2017/02/leetcode-10-regular-expression.html
» Longest Increasing Subsequence
http://rainykat.blogspot.com/2017/01/lintcode-longest-increasing-subsequence.html
» 198. House Robber LinkedIn Airbnb
https://leetcode.com/problems/house-robber/

can not break in 2 adjacent house, use dp[i][0],dp[i][1]  (0 no rob, 1 rob)
for(int i =1;i<=nums.length;i++){ //dp index 1 ahead of nums bc ini col 0
    dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
    dp[i][1] = dp[i-1][0] + nums[i-1]//must not rob pre house
}