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);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • dp 类找零钱类问题

    这类问题,需要维护,之前的状态,当前的状态是 (当前 - 当前值) 的上一个状态的最值相关

    黑白格
  • 动态规划设计

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

    黑白格
  • 网易校招真题三

    题目描述 又到了丰收的季节,恰逢小易去牛牛的果园里游玩。 牛牛常说他对整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛。 在果园里有N堆苹果,...

    黑白格
  • LintCode 解码方法题目分析代码

    样例 给你的消息为12,有两种方式解码 AB(12) 或者 L(12). 所以返回 2

    desperate633
  • 详解三道一维的动态规划算法题

    在一条直线上,有n个房屋,每个房屋中有数量不等的财宝,有一个盗 贼希望从房屋中盗取财宝,由于房屋中有报警器,如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...

    帅地
  • LintCode 最长上升子序列题目分析

    给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。 说明最长上升子序列的定义: 最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的...

    desperate633
  • Leetcode 1444. 切披萨的方案数(DP,类似石材切割,二维前缀和)

    给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次...

    glm233
  • dp 类找零钱类问题

    这类问题,需要维护,之前的状态,当前的状态是 (当前 - 当前值) 的上一个状态的最值相关

    黑白格
  • LintCode 最长公共子序列题目分析代码

    典型的动态规划问题 dp[i][[j]:表示前i个和前j个字符最大LCS 当A[i] = B[i]的时候: 那么显然dp[i][j] = dp[i-1][...

    desperate633
  • 每日算法系列【LeetCode 926】将字符串翻转到单调递增

    如果一个由 '0' 和 '1' 组成的字符串,是以一些 '0'(可能没有 '0')后面跟着一些 '1'(也可能没有 '1')的形式组成的,那么该字符串是单调递增...

    godweiyang

扫码关注云+社区

领取腾讯云代金券