研究生學(xué)過DP，當(dāng)時覺得還挺簡單的烛恤，就是從初始狀態(tài)開始母怜，找到推導(dǎo)公式一步步往下推嘛。但實際刷題時發(fā)現(xiàn)DP還是很難的缚柏，有時候想不到或者理不清推導(dǎo)的邏輯苹熏。今天筆試了一家大公司，兩道編程題全是dp問題币喧，而且leetcode上全有但是當(dāng)時覺得挺難所以跳過了轨域，現(xiàn)在還是要還的。

1.通配符wildcard

借用leetcode上的題目描述：

Implement wildcard pattern matching with support for '?' and ''.

'?' Matches any single character.
'' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char s, const char p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "") ? true
isMatch("aa", "a") ? true
isMatch("ab", "?") ? true
isMatch("aab", "ca*b") ? false

這時候就可以用一個二維數(shù)組儲存dp結(jié)果杀餐，dp[i][j]表示s的前i位和p的前j位的字符串的匹配結(jié)果干发。
初始化dp[i][0]和dp[0][j]。
dp[i][j] = true當(dāng)出現(xiàn)以下之一情況:
1.dp[i-1][j] == true && p[j-1] == '*'史翘，因為通配符最后一位是所以s隨便加一個沒關(guān)系啦枉长；
2.dp[i][j-1] == true && p[j-1] == '*'，因為加的是這個無所謂所以還是成立啦琼讽；
3.dp[i-1][j-1] == true && s[i-1] == p[j-1]搀暑，通配符和字符串加個一樣的字符還是成立啦。
4.dp[i-1][j-1] == true && p[j-1] == '*'或'?'跨琳。
其他情況dp[i][j]就為false啦。

 public static boolean isMatch(String s, String p) {
        
        
        int sLength = s.length();
        int pLength = p.length();
    
        
        char[] sChar = s.toCharArray();
        char[] pChar = p.toCharArray();
        
        
        boolean[][] dp = new boolean[sLength + 1][pLength + 1];
        
        dp[0][0] = true;

        for(int i = 1; i < sLength + 1; i++){
            dp[i][0] = false;
        }
        
        for(int j = 1; j < pLength + 1; j++){
            if(dp[0][j-1] && pChar[j-1] == '*') dp[0][j] = true;
            else dp[0][j] = false;
        }
        
        for(int i = 1; i < sLength + 1; i++){
            for(int j = 1; j < pLength + 1; j++){
                if((pChar[j-1] == '*' && (dp[i-1][j] || dp[i][j-1])) ||
                   (dp[i-1][j-1] && (pChar[j-1] == '*' || pChar[j-1] == '?' || pChar[j-1] == sChar[i-1]))){
                    dp[i][j] = true;
                }else{
                    dp[i][j] = false;
                }
            }
       
         return dp[sLength][pLength];      
        
    }

2.最長上升子序列Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

建立dp數(shù)組桐罕，dp[i]儲存的是以a[i]為結(jié)尾的最長上升子序列的長度脉让。
初始dp[0] = 0。
dp[i] = 1 + Max {dp[j]} s.t. j < i && a[j] < a[i]功炮。
注意最后求得的是dp中的最大值溅潜，因為最大值不一定是以最后一個數(shù)結(jié)尾的最大上升子序列哦。

public int lengthOfLIS(int[] nums) {
    
    if(nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    
    dp[0] = 1;
           
    for(int i = 1; i < nums.length; i++){
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(dp[j] >= dp[i] && nums[i] > nums[j]){
                 dp[i] = dp[j] + 1;
            }
        }
    }
    
    int res = 1;
    for(int i = 1; i < nums.length; i++){
        if(res < dp[i]){
            res = dp[i];
        }
    }
    
    return res;
}