300. Longest Increasing Subsequence

寻找上升的序列是可以有间隔的 ~ 我们用DP[ i ]表示到达i 点最长的上升子序列 和前面的 i - 1个点有关 如果当前的

A[ i ] > A[ j ] ( j < i ) 则我们可以更新 A[ i ] = A[ j ] + 1 我们要取这里面的最大值~

    public int lengthOfLIS(int[] nums) {
        //corner case 
        if(nums == null || nums.length == 0)return 0;
        int len = nums.length; 
        int[] P = new int[len];
        //base case
        Arrays.fill(P,1);
        int max = 1;
        for(int i = 1;i < len;i++){
            for(int j = 0;j < i;j++){
                if(nums[j] < nums[i]){
                    P[i] = Math.max(P[i],P[j] + 1);
                }
            }
            max = Math.max(max,P[i]);
        }
        return max;
    }

这道题也可以用Binary Search做 但是。。但是这个思路我是没想到

91. Decode Ways

改了一下做法 这个做法非常好理解 但是需要用到大量的substring 到每一位i的构造数目肯定是和前面的位数有关的 如果前面两位是在范围之内的 则加上dp[i - 2]的结果 如果前面的一位是合法的 则也可以加上 dp[i - 1]的 主要还是要找前后sub problem之间的关系

Pay attention to the base case: empty string have one way to decode

public class Solution {
    //dp[i] the number of decode ways ending at index i
    public int numDecodings(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        //base case empty string have one way to decode
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0'? 0 : 1;
        for(int i = 2;i <= n;i++){
            int one = Integer.valueOf(s.substring(i-1,i));
            int two = Integer.valueOf(s.substring(i-2,i));
            if(one >= 1 && one <= 9){
                dp[i] += dp[i-1];
            }
            if(two >= 10 && two <=26){
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
}