分类dp

乘积最大子数组
https://leetcode-cn.com/problems/maximum-product-subarray

思路：
暴力原始
三层循环
1层循环开始 2层循环结束 3层循环区间和

二层循环
1层循环开始，2层循环以一层循环+1开始循环到结束

一层循环
num = [2, -1, -2]
定义状态转移方程： dp[i] 表示以索引i为结束端点的连续区间最大乘积
dp = [2, -1, 4]
得出 dp[i]和dp[i-1]无关
dp[i] = max(num[i], num[i] * dp[i-1])

因为本题有负值。所以需要考虑分类的情况。

dp1[0] = arr[0]
dp2[0] = arr[0]

最大
if(arr[i] > 0)
最大正数 = 正数 * 前一个最大的正数
dp1[i] = Max(arr[i], dp1[i-1] * arr[i])
最小负数 = 正数 * 前一个最小的负数
dp2[i] = Max(arr[i], dp2[i-1] * arr[i])

最小
if(arr[j] <= 0)
最大正数 = 负数数 * 前一个最大的负数
dp1[i] = Max(arr[i], dp2[i-1] * arr[i])
最大负数 = 负数数 * 前一个最大的正数
dp2[i] = Max(arr[i], dp1[i-1] * arr[i])

ans = Max(dp1[i], ans);

 

class Solution {
    public int maxProduct(int[] nums) {
        int[] max = new int[2];
        int[] min = new int[2];
        max[0%2] = nums[0];
        min[0%2] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] > 0) {
                max[i%2] = Math.max(nums[i],nums[i]*max[(i-1)%2]);
                min[i%2] = Math.min(nums[i],nums[i]*min[(i-1)%2]);
            } else {
                max[i%2] = Math.max(nums[i],nums[i]*min[(i-1)%2]);
                min[i%2] = Math.min(nums[i],nums[i]*max[(i-1)%2]);
            }
            ans = Math.max(ans, max[i%2]);
        }

        return ans;
    }
}

 

滚动数组的最小三角形应用

最小三角形 滚动数组应用
https://leetcode-cn.com/problems/triangle/

 

dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j]);

滚动数组应用
倒序j的循环
dp[j] = triangle[i][j] + min(dp[j-1],dp[j])
//倒序保证了dp[j]是从i-1行得到结果，而且未被改变。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0){
            return 0;
        }
        // 加1可以不用初始化最后一层
        // int[][] dp = new int[triangle.size()+1][triangle.size()+1];

        // for (int i = triangle.size()-1; i>=0; i--){
        //     List<Integer> curTr = triangle.get(i);
        //     for(int j = 0 ; j < curTr.size(); j++){
        //         dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + curTr.get(j);
        //     }
        // }

        // return dp[0][0];

        
        int n = triangle.size();
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = triangle.get(0).get(0);
        int ret = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if(dp[j] == Integer.MAX_VALUE) {
                    if(j>0)
                        dp[j]=dp[j-1] + triangle.get(i).get(j);
                    else
                        dp[j]=triangle.get(i).get(j);
                } else {
                    if(j>0)
                    dp[j]=Math.min(dp[j],dp[j-1]) + triangle.get(i).get(j);
                    else
                    dp[j]+= triangle.get(i).get(j);
                }

                if(i == n-1){
                    if(dp[j] < ret) ret = dp[j];
                }
            }
        }

        if(ret == Integer.MAX_VALUE) return dp[0];
        return ret;
    }
}

 

https://leetcode-cn.com/problems/russian-doll-envelopes/
2021/5/11
搬箱子 中文版.docx

使用索引树 / 使用dp+二分法

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int maxL = 0;
        int dp[] = new int[envelopes.length];
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o2[1]-o1[1] : o1[0]-o2[0];
            }
        });
        dp[0] = envelopes[0][1];
        for (int i = 1; i < envelopes.length; i++) {
            if(envelopes[i][1] > dp[maxL]) {
                dp[++maxL] = envelopes[i][1];
            } else {
                int idx = binarySearch(dp, 0, maxL, envelopes[i][1]);
                //int idx = binarySearch0(dp, 0, maxL, envelopes[i][1]);
                if(idx < 0) idx = 0;
                dp[idx] = envelopes[i][1];

            }
        }

        return maxL+1;
    }

    private int binarySearch(int[] envelopes, int s, int e, int curr) {
        while (s < e) {
            int mid = s + (e-s) / 2;

            if(envelopes[mid] < curr) {
                s = mid+1;
            } else {
                e = mid;
            }
        }

        return e;
    }

    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

}