投稿
  1. 首页
  2. PHP

【蓝桥杯Java组】带你刷爆常见动态规划模型

code • 2022-4-9 • PHP • 阅读 131

【蓝桥杯Java组】带你刷爆常见动态规划模型,第1张

🍋前言：

🌵🌵蓝桥杯就剩一天了，祝看到这篇文章的老铁们都有好成绩~

🌴🌴这里总结了一些动态规划的常见模型，最后一天拿来复习一波，万一中了呢🤣

🍍1.最大子段和

  • 最大子段和或者叫最大子数组和。


  • f(i)代表以第 i个数结尾的「连续子数组的最大和」，对数组中的任意一个位置 n u m s [ i ] nums[i] nums[i]，要么单独作为一个子段，要么和前面的子段合并,状态转移方程： f ( i ) = m a x ( f ( i − 1 ) + n u m s [ i ] , n u m s [ i ] ) f(i)=max{(f(i−1)+nums[i],nums[i])} f(i)=max(f(i−1)+nums[i],nums[i])。


🚀题目链接：LeetCode53.最大子数组和

🍦参考代码（Java）：

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < len; i++) {
            dp[i] = nums[i] + Math.max(dp[i -1], 0);
            max = Math.max(max, dp[i]);
        }
        return max;
    }   
}
🍓2.最长递增子序列

🚀题目链接：LeetCode300.最长递增子序列

  • 最长递增子序列Longest Increasing Subsequence，即LIS。


  • d p [ i ] dp[i] dp[i]表示选择 n u m s [ i ] nums[i] nums[i]，并且以 n u m s [ i ] nums[i] nums[i]结尾的最长上升子序列的长度。


  • 需要双层循环for i = 1 ~ nums.length，for j = 0 ~ i，如果 n u m s [ i ] > n u m s [ j ] nums[i] > nums[j] nums[i]>nums[j]，说明构成了一个递增对，状态转移： d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 ) dp[i] = max{(dp[i], dp[j] + 1)} dp[i]=max(dp[i],dp[j]+1)，最后返回 d p dp dp数组中的最大值即为答案。


🍦参考代码（Java）：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        //base case : dp[0] = 1;
        for (int i = 1;i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[j] < nums[i])
                    dp[i] = Math.max(dp[j]+1,dp[i]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n;i++)
            ans = Math.max(ans,dp[i]);
        return ans;
    }
}
🍊3.最长公共子序列

🚀题目链接：LeetCode1143.最长公共子序列

  • 最长公共子序列 Longest Common Subsequence，即LCS。


  • 题目涉及两个字符串，使用二维dp[][]，dp[i][j]表示第一个字符串的0~i前缀子串与第二个字符串的0~j前缀子串的最长公共子序列。


  • 若第一个字符串的i位置与第二个字符串的j位置的两个字符相等，则 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i - 1][j - 1] + 1 dp[i][j]=dp[i−1][j−1]+1，若两个位置的字符不等则 d p [ i ] [ j ] dp[i][j] dp[i][j]取 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j]与 d p [ i ] [ j − 1 ] dp[i][j - 1] dp[i][j−1]的最大值。


  • 状态转移方程：

🍦参考代码（Java）：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
}
🍈4.编辑距离

🚀题目链接：LeetCode72.编辑距离

  • 题目涉及两个字符串，使用二维dp[][]。


  • d p [ i ] [ j ] dp[i][j] dp[i][j]表示word1的前i个字母转换成word2的前j个字母所使用的最少 *** 作。


  • 若 w o r d [ i ] = w o r d [ j ] word[i] = word[j] word[i]=word[j]，状态转移： d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i - 1][j - 1] dp[i][j]=dp[i−1][j−1]。


  • 若 w o r d [ i ] ≠ w o r d [ j ] word[i] \not= word[j] word[i]​=word[j]，说明当前位置需要一次修改，再加上之前需要修改的次数，则状态转移： d p [ i ] [ j ] = m i n ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ) + 1 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1 dp[i][j]=min(dp[i][j−1],dp[i−1][j],dp[i−1][j−1])+1

🍦参考代码（Java）：

class Solution {
    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 = 1; i <= len1; i++)
            dp[i][0] = i;
        for (int i = 1; i <= len2; i++)
            dp[0][i] = i;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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];
    }
}

🍑5. 01背包问题

🚀题目链接：https://oj.czos.cn/p/1282

题目描述

有一个背包能装的重量maxw(正整数，0≤maxw≤20000)，同时有n件物品(0≤n≤100)，每件物品有一个重量wi(正整数)和一个价值pi(正整数)。


要求从这n件物品中任取若干件装入背包内，使背包的物品价值最大。


输入

第1行：背包最大载重maxw，物品总数n
第2行到第n+1行：每个物品的重量和价值

输出

一个数字即背包内物品最大价值

样例：

输入

10 3
4 5
3 4
6 9

输出

14
  • 二维dp[][]，dp[i][j]对于前i个物品，放在背包，重量不超过j的前提下，所获得的最大价值为dp[i][j]。


  • 当第i个物品的重量大于j，说明放不进去，状态转移： d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i - 1][j] dp[i][j]=dp[i−1][j]。


  • 当第i个物品的重量小于j，说明可以装包，设第i个物品的重量为 c i c_i ci​，重量 w i w_i wi​，状态转移： d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c i ] + w i ） dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - c_i] + w_i） dp[i][j]=max(dp[i−1][j],dp[i−1][j−ci​]+wi​）。


🍦参考代码（Java）：

import java.util.Scanner;

public class Main {

    public static int n;
    public static int maxw;
    public static int[] w = new int[105];
    public static int[] p = new int[105];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        maxw = sc.nextInt();
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            p[i] = sc.nextInt();
        }
        int[][] dp = new int[n + 1][maxw + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= maxw; j++) {
                if (w[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
                }
            }
        }
        System.out.println(dp[n][maxw]);
        sc.close();
    }
}

🍸01背包优化（状态压缩）：

  • 由状态转移方程不难发现，对于dp[i][...]只和它的上一行dp[i - 1][...]有关系，可以在空间上做一下优化。


  • 可以使用一个一维数组滚动记录dp[i][...]的上一行数据。


  • 在一维数组上要从后向前推导，不然dp[i][j]的值会被覆盖掉，向后推会出错。


  • 状态转移返程为： d p [ j ] = m a x ( d p [ j ] , p [ i ] + d p [ j − w [ i ] ] ) dp[j] = max(dp[j],p[i] + dp[j - w[i]]) dp[j]=max(dp[j],p[i]+dp[j−w[i]])

🍦参考代码（Java）：

import java.util.Scanner;

public class Main {

    public static int n;
    public static int maxw;
    public static int[] w = new int[105];
    public static int[] p = new int[105];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        maxw = sc.nextInt();
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            p[i] = sc.nextInt();
        }
        int[] dp = new int[maxw + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = maxw; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i]);
            }
        }
        System.out.println(dp[maxw]);
        sc.close();
    }
}
🍐6.多重背包问题

🚀题目链接：https://oj.czos.cn/p/1888

题目描述

有 N N N种物品和一个容量是 V V V的背包。



第i种物品最多有 S i S_i Si​件，每件体积是 V i V_i Vi​，价值是 W i W_i Wi​。



求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。



输出最大价值。


输入

第一行两个整数， N N N， V V V，用空格隔开，分别表示物品种数和背包容积。


接下来有 N N N 行，每行三个整数 v i , w i , s i v_i,w_i,s_i vi​,wi​,si​，用空格隔开，分别表示第 i 种物品的体积、价值和数量。


0 < N , V ≤ 100 00<N,V≤100
0 < v i , w i , s i ≤ 100 00<vi​,wi​,si​≤100

输出

输出一个整数，代表最大价值。


样例

输入

4 10
3 2 2
4 3 2
2 2 1
5 3 4

输出

8
  • 将多重背包转换为01背包。


  • 将 S i S_i Si​件物品都存起来，转换为有 S i S_i Si​个物品，每个物品有一件。


  • 这里并不需要改变dp[][]数组的长度从而真的将物品拆分成一件，只需要在01背包的基础上加一层循环即可。


🍦参考代码（Java）：

import java.util.Scanner;

public class Main {

    public static int n;
    public static int v;
    public static int[] v_i = new int[105];
    public static int[] w_i = new int[105];
    public static int[] s_i = new int[105];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        v = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            v_i[i] = sc.nextInt();
            w_i[i] = sc.nextInt();
            s_i[i] = sc.nextInt();
        }
        int[] dp = new int[v + 1];
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= s_i[i]; k++) {
                for (int j = v; j >= v_i[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - v_i[i]] + w_i[i]);
                }
            }
        }
        System.out.println(dp[v]);
    }
}
🍏7.完全背包问题

🚀题目链接：https://oj.czos.cn/p/1780

题目描述

仙岛上种了无数的不同种类的灵芝，小芳跟着爷爷来到仙岛采摘灵芝。


由于他们带的食物和饮用水有限，必须在时间t内完成采摘。



假设岛上有m种不同种类的灵芝，每种灵芝都有无限多个，已知每种灵芝采摘需要的时间，以及这种灵芝的价值；
请你编程帮助小芳计算，在有限的时间t内，能够采摘到的灵芝的最大价值是多少？

输入

输入第一行有两个整数T（1 <= T <= 100000）和M（1 <= M <= 2000），用一个空格隔开，T代表总共能够用来采灵芝的时间，M代表岛上灵芝的种类数。


接下来的M行每行包括两个在1到10000之间（包括1和10000）的整数，分别表示采摘某种灵芝的时间和这种灵芝的价值。


输出

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的灵芝的最大总价值。


样例

输入

70 3
71 100
69 1
1 2

输出

140
  • 题目完全可以看成是背包问题，时间相当于背包问题的体积，不过与01背包的区别在于物品有无限个，这种背包叫做完全背包。


⭐回顾一下01背包：

  • 设物品重量 w i w_i wi​，价值 v i v_i vi​,01背包的状态转移方程： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) f[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + v[i]) f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])。


  • 转换为一维滚动数组的状态转移方程： f [ j ] = m a x ( f [ j ] , f [ j − w [ i ] ] + v [ i ] ) f[j] = max(f[j],f[j - w[i]] + v[i]) f[j]=max(f[j],f[j−w[i]]+v[i])。


⭐接下来试着推到完全背包的状态转移方程：

  1. 设物品件数为 k k k，可以想到完全背包的状态转移方程： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − k × w [ i ] ] + k × v [ i ] ) f[i][j] = max(f[i - 1][j],f[i - 1][j - k \times w[i]] + k \times v[i]) f[i][j]=max(f[i−1][j],f[i−1][j−k×w[i]]+k×v[i])，限制条件 1 < = k < = w / w [ i ] 1 <= k <= w/w[i] 1<=k<=w/w[i]，此时需要三重循环。


  2. k = 0 k = 0 k=0代表不取第i件物品，转移方程化简为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j − k × w [ i ] ] + k × v [ i ] ) f[i][j] = max(f[i - 1][j - k \times w[i]] + k \times v[i]) f[i][j]=max(f[i−1][j−k×w[i]]+k×v[i])。


  3. 或者把 k = 0 k = 0 k=0的情况单独拿出来考虑，状态转移方程为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , m a x ( f [ i − 1 ] [ j − k × w [ i ] ] + k × v [ i ] ) ) f[i][j] = max(f[i - 1][j],max(f[i - 1][j - k \times w[i]] + k \times v[i])) f[i][j]=max(f[i−1][j],max(f[i−1][j−k×w[i]]+k×v[i]))
  4. 考虑上式放第i种物品的情况，放的话至少放一件，先把这一件放进去，状态转移方程变型为：
    f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , m a x ( f [ i − 1 ] [ ( j − w [ i ] ) − k × w [ i ] ] + k × v [ i ] ) + v [ i ] ) f[i][j] = max(f[i - 1][j],max(f[i - 1][(j - w[i]) - k \times w[i]] + k \times v[i]) + v[i]) f[i][j]=max(f[i−1][j],max(f[i−1][(j−w[i])−k×w[i]]+k×v[i])+v[i])
  5. 将第 2 2 2步的式子中的j换成j - w[i]得到： f [ i ] [ j − w [ i ] ] = m a x ( f [ i − 1 ] [ ( j − w [ i ] ) − k × w [ i ] ] + k × v [ i ] ) f[i][j - w[i]] = max(f[i - 1][(j - w[i]) - k \times w[i]] + k \times v[i]) f[i][j−w[i]]=max(f[i−1][(j−w[i])−k×w[i]]+k×v[i])，结合第 4 4 4步的式子得到：
    f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − w [ i ] ] + v [ i ] ) f[i][j] = max(f[i - 1][j],f[i][j - w[i]] + v[i]) f[i][j]=max(f[i−1][j],f[i][j−w[i]]+v[i])
    发现 k k k已经被消掉了，只需要双重循环就可以解决问题，跟01背包的状态转移方程只有一处差别，f[i - 1][j - w[i]] + v[i] 变为 f[i][j - w[i]] + v[i]。


⭐完全背包的状态转移方程已经和01背包很像了，到了这里如何做一维数组滚动优化呢？

  • 考虑到跟01背包状态转移方程的差别，计算第i行时不需要保留第i - 1行的数据了，因此只需要从当前物品的重量 w i w_i wi​正序循环至背包容量 c c c，状态转移方程完全不变。



    d p [ j ] = m a x ( d p [ j ] , d p [ j − w [ i ] ] + v [ i ] ) dp[j] = max(dp[j],dp[j - w[i]] + v[i]) dp[j]=max(dp[j],dp[j−w[i]]+v[i])

🍦参考代码（Java）：

import java.util.Scanner;

public class Main {

    public static int t;
    public static int m;
    public static int[] t_i = new int[2005];
    public static int[] v_i = new int[2005];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= m; i++) {
            t_i[i] = sc.nextInt();
            v_i[i] = sc.nextInt();
        }
        int[] dp = new int[t + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = t_i[i]; j <= t; j++) {
                dp[j] = Math.max(dp[j], dp[j - t_i[i]] + v_i[i]);
            }
        }
        System.out.println(dp[t]);
    }
}

🍌🍌🍌
动态规划的常见模型+背包问题都在这里啦~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。


🙇🏻‍♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲一枚，请大佬们多多关照~

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/567567.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-09
下一篇 2022-04-09

发表评论

登录后才能评论

评论列表（0条）

保存