dp经典问题

1. 最长子序列问题

最长上升不连续子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

// 最长上升不连续子序列，可以使用dp[j]，来表示前j个数的最长上升子序列，那么需要维护一个max来统计最大值
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for(int i=1;i<nums.length;i++){
            int curMax = 0;
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]){
                    curMax = Math.max(curMax,dp[j]);
                }
            }
            dp[i] = curMax + 1;
            max = Math.max(dp[i],max);
        }
        return max;
    }

// 当然更快速的方法是使用二分查找进行插入

递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

这里采用组合回溯的方法：

组合回溯模板主要用于生成非全排列的子集，同时可以用来尝试数值

组合回溯的模板

// 这里使用preIndex可以避免已经选过的，再次给当前位置赋值
// 每一次回溯实际是给当前位置curPos 进行赋值操作
public void backTrack(int[] nums,int curPos,int preIndex){
    // 递归出口
    if(curPos == k){
        // 本题没有在这里return主要是由于，生成所有子集
        return;
    }
    // 这里实际类似于给当前位置赋值
    //backTrack(nums[curPos]=x1,curPos+1....)
    //backTrack(nums[curPos]=x2,curPos+1....)
    //backTrack(nums[curPos]=x3,curPos+1....)
    for(int i=preIndex+1;i<nums.length;i++){
        // 这里可以添加各种判断 
        // hashSet保证 当前位置不赋值相同的数，避免结果出现相同值，nums[curPos] = x;
        backTrack(nums,curPos+1,i);
        // 数组不需要回溯，直接赋值覆盖即可
    }
}

 List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 枚举
        if(nums == null || nums.length == 0){
            return res;
        }
        backTrack(nums,new int[nums.length],0,-1,Integer.MIN_VALUE);
        return res;
    }

    public void backTrack(int[] nums,int[] tmp,int curPos,int preIndex,int pre){
        if(curPos >1){
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<curPos;i++){
                list.add(tmp[i]);
            }
            res.add(list);
        }

        HashSet<Integer> set = new HashSet<>();
        for(int i=preIndex+1;i<nums.length;i++){
            if(!set.contains(nums[i]) && pre <= nums[i]){
                tmp[curPos] = nums[i];
                set.add(nums[i]);
                backTrack(nums,tmp,curPos+1,i,nums[i]);
            }
        }
    }

最长递增子序列的个数

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5

求最大长度的个数，实际是基于最大长度算法 进行更新

dp[i] 代表 dp[i] 以i结尾的子序列的最大长度，因为这里需要统计 最大长度的个数，思路是 某一个位置j num[j] < num[i] 的情况下， dp[j] > dp[i] , dp[i] 的 最大长度是dp[j] + 1, 那么他的最大个数是 count[i] += count[j] , 例如

1234 7 1235 7

 // 思路，使用length 数组，记录，当前位置的最大长度，count[i] 统计当前位置最大长度的次数
    public int findNumberOfLIS(int[] nums) {
        if(nums == null || nums.length <= 1 ){
            return nums.length;
        }

        int[] count = new int[nums.length];
        int[] length = new int[nums.length];
        Arrays.fill(count,1);
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]){
                    if(length[j] >= length[i]){
                        length[i] = length[j] + 1;
                        count[i] = count[j];
                    }else if(length[j] + 1 == length[i]){
                        count[i] += count[j];
                    }
                }
            }
        }
        // 找到最长位置的index,返回最长位置数量
        int maxLength = 0;
        for(int i=0;i<nums.length;i++){
            if(maxLength < length[i]){
                maxLength = length[i];
            }
        }
        int ans = 0;
        for(int i=0;i<nums.length;i++){
            if(maxLength == length[i]){
                ans += count[i];
            }
        }
        return ans;
    }

2.背包问题

背包问题就是选与不选的问题，问 容量w 和 物品 n 下选择最多价值，就先求1,1 ，12 ，等情况，反向递推

  public int packet(int n, int k, int[] w,int[] v){
        int[][] dp = new int[n+1][k+1];
        for(int i=1;i<=n;i++){
            for (int j=1;j<=k;j++){
                if(j > w[i]){
                    dp[i][j] = Math.max(dp[i-1][j-w[i]] + v[i],dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][k];
    }

零钱兑换问题

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1

 public int coinChange(int[] coins, int amount) {
        // 零钱兑换，就动态规划，找到兑换i的最少钱数
        // dp[i] = min 遍历 dp[i-coins[j]] + 1
        if(coins == null || coins.length == 0){
            return -1;
        }
        int[] dp = new int[amount+1];
        for(int i=1;i<=amount;i++){
            // 这里最小的找钱次数是 amount + 1, 不要乱改
            int min = amount+1;
            for(int j=0;j<coins.length;j++){
                if(coins[j]<=i)
                min = Math.min(min,dp[i-coins[j]]+1);
            }
            dp[i] = min;
        }
        if (dp[amount] == amount+1){
            return -1;
        }
        return dp[amount];
    }

零钱兑换问题2

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

零钱兑换问题2 是完全背包问题

暴力求解

 public int change(int amount, int[] coins) {
        // 零钱兑换问题
        int[][] dp = new int[coins.length+1][amount+1];
        dp[0][0] = 1;
        for (int i=1;i<=coins.length;i++){
            for (int j=0;j<=amount;j++){
                for (int k=0;k*coins[i-1]<=j;k++){
                    dp[i][j] += dp[i-1][j-k*coins[i-1]];
                }
            }
        }
        return dp[coins.length][amount];
    }

再次进行优化， dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];

完全背包

public int change(int amount, int[] coins) {
        // 零钱兑换问题
        int[][] dp = new int[coins.length+1][amount+1];
        for (int i=0;i<=coins.length;i++){
            dp[i][0] = 1;
        }
        for (int i=1;i<=coins.length;i++){
            for (int j=0;j<=amount;j++){
               dp[i][j] = dp[i-1][j];
               if(j > coins[i-1]){
                   dp[i][j] += dp[i][j-coins[i-1]];
               }
            }
        }
        return dp[coins.length][amount];
    }

将方法2中的dp[i][j] =dp[i - 1][j]+ dp[i][j - coins[i - 1]];dp[i][j]=dp[i−1][j]+dp[i][j−coins[i−1]];去掉一维ii得到，dp[j]=dp[j+dp[j-coins[i]]]dp[j]=dp[j+dp[j−coins[i]]]这里ii从00开始的，不需要取coins[i-1]coins[i−1]

这里因为状态之和前一个状态相关可以取消

public int change3rd(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
}

分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

注意： 这里应该从后向前推导，防止数据重用，在只有前i个物品是 j为3 是减了一遍sum[i], j 为8 还要减一遍；

    // 实际上可以转化为，子集中是否存在是二分之一的子集
    // 采用枚举的方法进行dfs搜索
   public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }
        int sum = 0;
        for(int x:nums){
            sum += x;
        }
        if(sum % 2 == 1){
            return false;
        }
        // 子集分割实际为背包问题的变体
        boolean[] dp = new boolean[sum/2+1];
        dp[0] = true;
        for(int i=0;i<nums.length;i++){
            // 状态压缩后要注意遍历的顺序，这里每一个数字只能使用一次，所以应该从后往前推导
            for(int j=sum/2;j>=1;j--){
                if(j >= nums[i]){
                    dp[j] = dp[j] | dp[j-nums[i]];
                }
            }
        }
        return dp[sum/2];
    }

72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

 public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        
        int[][] dp = new int[len1+1][len2+1];

        for(int i=0;i<=len1;i++){
            dp[i][0] = i;
        }
        for(int i=0;i<=len2;i++){
            dp[0][i] = i;
        }
        for(int i=1;i<len1+1;i++){
            for(int j=1;j<len2+1;j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
                }
            }
        }
        return dp[len1][len2];
    }

高楼扔鸡蛋

若⼲层楼，若⼲个鸡蛋，让你算出最少的 尝试次数，找到鸡蛋恰好摔不碎的那层楼。

public int dp(int k, int n){
    int res = n + 1;
    for(int i=1;i<=n;i++){
        res = min(res,max(dp(k-1,i-1),dp(k,n-i))+1);
    }
}