300. 最长递增子序列

• 朴素法

  class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //dp[i]表示以i结尾的上升子序列的最大的长度
        //dp[i] = max{dp[k]} + 1，满足nums[k]<nums[i],k < i
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return max;
    }
  }

• 贪心+二分查找

  class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] res = new int[nums.length];
        int tail = 0;
        res[tail] = nums[tail];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > res[tail]) {
                res[++tail] = nums[i];
            } else {
                //找第一个大于等于nums[i]的元素 1,2,5,7,9 
                int l = 0, r = tail;
                while (l <= r) {
                    int mid = l + (r - l) / 2;
                    if (res[mid] < nums[i]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }     
                }
                res[l] = nums[i];
            }
        }
        return tail + 1;
    }
  }
  

  70. 爬楼梯

  

  class Solution {
    public int climbStairs(int n) {
        if (n < 2) return 1;
        int[] dp = new int[n + 1];
        //dp[i] = dp[i - 1] + dp[i - 2]
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
  }
  

• 压缩空间

  class Solution {
    public int climbStairs(int n) {
        if (n < 2) return 1;
        int one = 1, two = 1;
        for (int i = 2; i <= n; i++) {
            int tmp = two;
            two = one + two;
            one = tmp;
        }
        return two;
    }
  }
  

  198. 打家劫舍

  

  class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        //dp[i][0]表示是前i个房间，抢第i个房间的最大金额
        int[][] dp = new int[n][2];
        dp[0][0] = nums[0];//抢
        dp[0][1] = 0;//不抢
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][1] + nums[i];
            dp[i][1] = Math.max(dp[i - 1][0],dp[i - 1][1]);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
   }
  }
  

  221. 最大正方形

  
  思路：dp[i][j]=min{dp[i-1][j-1],dp[i-1][j],dp[i][j-1]} + 1
  

  class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        //dp[i][j]表示以i,j为右下角的符合条件的正方形边长
        //方程:dp[i][j]=min{dp[i-1][j-1],dp[i-1][j],dp[i][j-1]} + 1, 当matrix[i][j]==1时
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (matrix[i - 1][j - 1] != '1') continue;
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                max = Math.max(max, dp[i][j] * dp[i][j]);
            }
        }
        return max;
    }
  }
  

  279. 完全平方数

  

  class Solution {
    public int numSquares(int n) {
        if (n < 1) return 0;
        //dp[i]表示凑成i所需要的最少个数
        //dp[i]=min{dp[i-k*k]}+1,k=1,2,3,4...
        int[] dp = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            int min = i;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }
  }
  

  11. 盛最多水的容器

  

  class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) return 0;
        int max = 0;
        int l = 0, r = height.length - 1;
        while (l < r) {
            max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return max;
    }
  }