338. 比特位计数 

//枚举的话  nlogn的

//n 的话 ：
//用之前计算的结果

//f[n]:  f[n/2]算过了  
//f[n] = f[n/2] + 1(奇数时候加一)

class Solution {
    public int[] countBits(int num) {
        if (num == 0)
            return null;
        int[] dp = new int[num + 1];
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            dp[i] = dp[i>>1] + (i & 1);//如果i是奇数时候， 加上1
        }
        return dp;
    }
}

322. 零钱 

class Solution {
    public int coinChange(int[] coins, int amount) {

        int [] f = new int[amount + 1];
        f[0] = 0;

        for(int i = 1; i <= amount; i++){

            int cost = Integer.MAX_VALUE;   //此目标值下的  硬币个数  //cost用于存储每个目标值的dp[i]

            for(int j = 0; j < coins.length; j++){
                if(i - coins[j] >= 0){  //如果能填这个硬币
                    if(f[i-coins[j]] != Integer.MAX_VALUE) // 如果上一个存在           
                        cost = Math.min(cost, f[i - coins[j]] + 1);
                }
            }  

            f[i] = cost;     //赋值
        }

        return  f[amount] == Integer.MAX_VALUE? -1 : f[amount];
    }
}

221. 最大正方形 

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length <= 0 ||matrix[0] == null || matrix[0].length <= 0)
            return 0;
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n][m];              //dp中存放最大边长
        int res = 0;
        //dp[0][0] = Integer.valueOf(matrix[0][0]);
        for (int i = 0; i < n ; i++){
            for (int j = 0; j < m; j++){
                if (matrix[i][j] == '0')
                    dp[i][j] = 0;
                else{
                    dp[i][j] = 1;
                    if (i >= 1 && j >= 1)
                        dp[i][j] += Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1]));   //边长取最小+1
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        
        return res * res;
    }
}

91. 解码方法 

// f[i]: 截至第i位有多少

// f[i] = 1. f[i]  可否表示(>0) ：f[i] += f[i -1]
//2. f[i]和f[i-1]可否表示(10-26) : f[i] += f[i -2]

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() <= 0)
            return 0;
        int len = s.length();
        int[] dp = new int[len + 1];
        s = ' ' + s;
        dp[0] = 1;  //第一个位置的前面，初始化位一
        for (int i = 1; i <= len; i++){
            dp[i] = 0;
            if (s.charAt(i) != '0')
                dp[i] += dp[i - 1];  //自己单独一位
            if(i > 1){
                int t = (s.charAt(i - 1) - '0') *10 + (s.charAt(i) - '0');  //得数字
                if (t >= 10 && t <= 26)
                    dp[i] += dp[i - 2];
            }
        }
        return dp[len];
    }
}

263. 丑数 

class Solution {
    public int nthUglyNumber(int n) {
        ArrayList<Integer> q = new ArrayList<Integer>();
        q.add(1);
        int i = 0, j = 0, k = 0;
        while (--n >0){
            int t = Math.min(q.get(i)*2,Math.min(q.get(j)*3, q.get(k)*5));
            q.add(t);
      
            if (q.get(i) * 2 == t) i++;
            if (q.get(j) * 3 == t) j++;
            if (q.get(k) * 5 == t) k++;
        }
        return q.get(q.size() - 1);
    }
}

115. 不同的子序列 

class Solution {
    //相同： f[i][j] = f[i -1][j - 1] + (不用)f[i -1][j];
    //不相同：f[i][j] = f[i -1][j];
    public int numDistinct(String s, String t) {
        if (s == null || t == null)
            return 0;
        int n = s.length(), m = t.length();
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i <= n; i++)  //初始化边界
            dp[i][0] = 1; //全不匹配
        
        for(int i = 1; i<=n; i++){
            for (int j = 1; j <=m; j++){
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j -1))
                    dp[i][j] += dp[i-1][j-1];
            }
        }
        
        return dp[n][m];
    }
}