300. 最长递增子序列

    “状态转移方程，是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。

    1.  public int lengthOfLIS(int[] nums) {
    2.         int dp[] = new int[nums.length];
    3.         Arrays.fill(dp, 1);
    4.         for (int i = 0; i < nums.length; i++) {
    5.             for (int j = 0; j < i; j++) {
    6.                 if (nums[i] > nums[j]) {
    7.                     dp[i] = Math.max(dp[i], dp[j] + 1);
    8.                 }
    9.             }
    11.         }
    13.         int res = 0;
    14.         for (int i = 0; i < dp.length; i++) {
    15.             res = Math.max(res, dp[i]);
    16.         }
    17.         return res;
    18.     }

    labuladong公众号

    1. // 二分查找
    2. int lengthOfLIS(int[] nums) {
    3.     int[] top = new int[nums.length];
    4.     // 牌堆数初始化为 0
    5.     int piles = 0;
    6.     for (int i = 0; i < nums.length; i++) {
    7.         // 要处理的扑克牌
    8.         int poker = nums[i];
    10.         /***** 搜索左侧边界的二分查找 *****/
    11.         int left = 0, right = piles;
    12.         while (left < right) {
    13.             int mid = (left + right) / 2;
    14.             if (top[mid] > poker) {
    15.                 right = mid;
    16.             } else if (top[mid] < poker) {
    17.                 left = mid + 1;
    18.             } else {
    19.                 right = mid;
    20.             }
    21.         }
    22.         /*********************************/
    24.         // 没找到合适的牌堆，新建一堆
    25.         if (left == piles) piles++;
    26.         // 把这张牌放到牌堆顶
    27.         top[left] = poker;
    28.     }
    29.     // 牌堆数就是 LIS 长度
    30.     return piles;
    31. }

    拓展二维 354. 俄罗斯套娃信封问题

    1.     public int maxEnvelopes(int[][] envelopes) {
    2.         Arrays.sort(envelopes, new Comparator<int[]>() {
    3.             @Override
    4.             public int compare(int[] o1, int[] o2) {
    5.                 return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
    6.             }
    7.         });
    8.         int[] height=new int[envelopes.length];
    9.         for (int i = 0; i <envelopes.length ; i++) {
    10.              height[i]=envelopes[i][1];
    11.         }
    13.         return lengthOfLIS(height);
    14.     }
    15.      public int lengthOfLIS(int[] nums) {
    16.         int dp[] = new int[nums.length];
    17.         Arrays.fill(dp, 1);
    18.         for (int i = 0; i < nums.length; i++) {
    19.             for (int j = 0; j < i; j++) {
    20.                 if (nums[i] > nums[j]) {
    21.                     dp[i] = Math.max(dp[i], dp[j] + 1);
    22.                 }
    23.             }
    25.         }
    27.         int res = 0;
    28.         for (int i = 0; i < dp.length; i++) {
    29.             res = Math.max(res, dp[i]);
    30.         }
    31.         return res;
    32.     }
        static int binarySearch(int w, int n, int[] wt, int[] val) {
        int[][] dp = new int[n + 1][w + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w; j++) {
                if (wt[i - 1] > j) {    //由于dp数组i要从1开始，所以w数组要减一，避免数组越界（dp[1]的时候w[0]）
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - wt[i - 1]] + val[i - 1], dp[i - 1][j]);
                }

            }

        }
        return dp[n][w];
    }

    public static void main(String[] args) {
        int[] wt = {2, 1, 3};
        int[] val = {4, 2, 3};
        System.out.println(binarySearch(4, 3, wt, val));
    }