^-^
I am who I am.
动态规划 - Dynamic Programming - 1
最近更新：2024-08-04   |   字数总计：6.4k   |   阅读估时：27分钟   |   阅读量：次
  1. 基础算法 - 动态规划 - 1
    1. 什么是动态规划？
    2. 动态规划的核心思想
  2. 相关题目
    1. 70. 爬楼梯 - 力扣（LeetCode）
    2. 53. 最大子数组和 - 力扣（LeetCode）
    3. 118. 杨辉三角 - 力扣（LeetCode）
    4. 198. 打家劫舍 - 力扣（LeetCode）
    5. 279. 完全平方数 - 力扣（LeetCode）
    6. 322. 零钱兑换 - 力扣（LeetCode）
    7. 139. 单词拆分 - 力扣（LeetCode）
    8. 300. 最长递增子序列 - 力扣（LeetCode）
    9. 152. 乘积最大子数组 - 力扣（LeetCode）
    10. 416. 分割等和子集 - 力扣（LeetCode）
    11. [P2871 USACO07DEC] Charm Bracelet S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
    12. P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
    13. 32. 最长有效括号 - 力扣（LeetCode）

基础算法 - 动态规划 - 1

在算法设计中，动态规划（Dynamic Programming，简称 DP）是一种通过将复杂问题分解为更小的子问题来求解的优化技术。它特别适用于具有重叠子问题和最优子结构性质的问题。

什么是动态规划？

动态规划是一种优化方法，用于解决具有重叠子问题和最优子结构性质的问题。重叠子问题意味着我们可以将一个问题分解为多个子问题，这些子问题会被多次计算。最优子结构则意味着问题的最优解可以由其子问题的最优解组合而成。通过保存子问题的解，我们可以避免重复计算，从而提高算法的效率。

动态规划的核心思想

动态规划的核心思想是记忆化和状态转移。我们可以将问题的解存储在一个表格中，当需要这个解时直接查表，而不是重新计算。这种方法避免了重复计算，大大提高了效率。通过将问题分解成更小的子问题来解决，并且通过记忆化来避免重复计算。

具体来说，动态规划的步骤可以总结为以下几步：

  1. 定义状态：确定问题的状态表示，并定义状态变量。通常，状态表示问题的一个子问题。
  2. 状态转移方程：找出不同状态之间的转移关系，形成状态转移方程。这个方程描述了如何通过子问题的解来构建更大问题的解。
  3. 初始化状态：根据问题的初始条件，设置初始状态的值。
  4. 计算状态：按照状态转移方程，从初始状态开始，逐步计算出每个状态的值，直到得到问题的最终解。

动态规划适用于以下几类问题：

  1. 最优子结构问题：问题的最优解可以通过其子问题的最优解组合而成。
  2. 重叠子问题问题：问题可以分解为多个子问题，这些子问题在计算过程中会被多次使用。

本篇博客记录刷题过程，学习过程中的思考和总结。

相关题目

70. 爬楼梯 - 力扣（LeetCode）

难度：简单

经典的动态规划问题。

基本思路是：到达第 n 级台阶的方法数，等于到达第 n-1 级台阶的方法数和到达第 n-2 级台阶的方法数之和。这是因为，如果我们要到达第 n 级台阶，我们可以从第 n-1 级台阶爬一阶上来，或者从第 n-2 级台阶爬两阶上来。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1; // 边界情况，如果只有1级台阶，则只有一种方法
        
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

重叠子问题：问题可以分解为规模较小的相同问题，即 climbStairs(n) 可以分解为 climbStairs(n-1) 和 climbStairs(n-2)，而 climbStairs(n-1) 和 climbStairs(n-2) 还可以继续分解。这些子问题是重叠的，即会被多次计算。通过动态规划，我们用数组 dp 来保存每个子问题的解，避免重复计算，从而提高效率。

53. 最大子数组和 - 力扣（LeetCode）

难度：简单

这个题可以用前缀和做，也可以用动态规划做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 动态规划
class Solution {
    public int maxSubArray(int[] nums){
        int len = nums.length;
        int[] dp = new int[len];  // dp[i]表示以nums[i]结尾的子数组的最大和 
        dp[0] = nums[0];
        int res = dp[0];
        for(int i=1;i<len;i++){
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            res = Math.max(dp[i],res);
        }
        return res;
    }
}

状态定义

定义 dp[i] 为以 nums[i] 结尾的子数组的最大和。

状态转移方程

  • 如果我们选择以 nums[i] 结尾的子数组，那么我们有两种选择：
    1. 只包含当前元素 nums[i]。
    2. 将当前元素 nums[i] 加入到以 nums[i-1] 结尾的子数组中。
  • 因此，状态转移方程为：dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);

118. 杨辉三角 - 力扣（LeetCode）

难度：简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();  // 存放杨辉三角的所有行
        for(int i=1;i<=numRows;i++){  // 从第1行开始生成，生成到第numRows行
            List<Integer> tmp = new ArrayList<>();  // 存放当前行的数字
            for(int j=0;j<i;j++){  // 当前行的长度为i，每一行有i个元素
                if(j==0||j==i-1){  // 每行的第一个和最后一个元素都是1
                    tmp.add(1);
                }else{
                    // 其他位置的元素是上一行的两个相邻元素之和
                    tmp.add(res.get(i-2).get(j-1) + res.get(i-2).get(j));
                }
            }
            res.add(tmp);  // 将当前行加入结果列表
        }
        return res;
    }
}

重叠子问题，生成杨辉三角的第 i 行的第 j 个元素时，需要用到第 i-1 行的第 j-1 和第 j 个元素，这些子问题在不同的行之间是重叠的。

198. 打家劫舍 - 力扣（LeetCode）

难度：中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        // 定义一个数组dp，用于存储到每个位置所能抢到的最大金额
        int[] dp = new int[len];
        
        // 初始化dp数组的前两个元素
        dp[0] = nums[0]; // 第一个房子只能抢劫这一个房子
        if(len == 1) return dp[0]; // 如果只有一个房子，则直接返回抢劫这一个房子的金额
        
        dp[1] = Math.max(nums[0], nums[1]); // 前两个房子，选择金额较大的一个抢劫
        
        // 从第3个房子开始计算，每个房子有两个选择
        for(int i = 2; i < len; i++) {
            // 选择1：抢劫当前房子，不能抢劫前一个房子，所以加上dp[i-2]
            // 选择2：不抢劫当前房子，保持前一个房子的最大金额dp[i-1]
            // 取两者中的最大值
            dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
        }
        
        // 返回抢劫到最后一个房子时的最大金额
        return dp[len-1];
    }
}

dp[i]：表示抢劫到第 i 个房子时，能抢到的最大金额。

对于每一个房子，有两个选择：

  1. 抢劫当前房子：此时不能抢劫前一个房子，因此最大金额为 dp[i-2] + nums[i]。
  2. 不抢劫当前房子：此时最大金额为 dp[i-1]。

因此，状态转移方程为： dp[i]=max⁡(dp[i−2]+nums[i],dp[i−1])

它利用了状态转移方程将问题分解成子问题，通过逐步求解每个子问题的最优解，最终得到整个问题的最优解。

279. 完全平方数 - 力扣（LeetCode）

难度：中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numSquares(int n) {
        // 定义一个dp数组，dp[i]表示数字i需要的最少完全平方数的个数
        int[] dp = new int[n + 1];
        
        // 遍历每一个从1到n的数字
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            // 遍历每一个可以用来组成i的平方数
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1; // 加1是因为我们用了一个平方数
        }
        
        // 返回数字n所需的最少完全平方数的个数
        return dp[n];
    }
}

定义状态

dp[i]：表示将正整数 i 表示为若干个平方数之和，所需的最少平方数的个数。

状态转移方程

对于每个 i，我们尝试每一个可能的平方数 j * j（其中 j 从 1 开始，直到 j * j 不超过 i），并且更新 dp[i] 的值，公式如下： dp[i]=min⁡(dp[i−j⋅j])+1 其中 dp[i - j * j] 表示去掉一个平方数 j * j 之后，剩余部分 i - j * j 所需要的最少平方数个数

题目性质分析

在本题中，求解 n 的最小完全平方数个数，可以分解为求解 n - j^2 的最小完全平方数个数，其中 j 是满足 j^2 <= n 的整数。

例如，求 dp[12]，可以分解为 dp[12-1^2], dp[12-2^2], dp[12-3^2]，即 dp[11], dp[8], dp[3]。这些子问题在求解其他数的最小完全平方数个数时也会出现，体现了重叠子问题的性质。具体来说，假设我们已经求出了 dp[i - j^2]，即 i - j^2 的最小完全平方数个数，那么 dp[i] 的值可以通过 dp[i - j^2] + 1 来更新。

322. 零钱兑换 - 力扣（LeetCode）

难度：中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.sort(coins);  // 对硬币面额进行排序
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i - coin < 0) break;  // 如果金额小于硬币面额，跳出循环
                if (dp[i - coin] != -1) {  // 如果dp[i-coin]有解
                    min = Math.min(min, dp[i - coin]);
                }
            }
            if (min != Integer.MAX_VALUE)
                dp[i] = min + 1;  // 更新dp[i]为最小值加1
            else
                dp[i] = -1;  // 如果无法凑出当前金额，设为-1
        }
        return dp[amount];
    }
}

在本题中，求解 amount 的最少硬币数，可以分解为求解 amount - coin 的最少硬币数，其中 coin 是硬币的面额。

本题和上一题几乎一模一样，使用动态规划来解决最小数量问题，但是本题所给出的硬币是固定的，并且存在拼凑不出amount的情况，需要特殊判断。

139. 单词拆分 - 力扣（LeetCode）

难度：中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1]; // dp[i] 表示 [0, i) 的字符串是否可以被表示
        dp[0] = true; // 空字符串是可以被拆分的

        // 将 wordDict 转换成一个 HashSet 以提高查询效率
        HashSet<String> set = new HashSet<>(wordDict);

        // 遍历字符串 s 的每一个位置 i
        for (int i = 0; i < len; i++) {
            // 如果 dp[i] 为 false，跳过当前循环
            if (!dp[i]) continue;

            // 从位置 i 开始继续遍历到位置 j，检查 s[i:j] 是否在 wordDict 中
            for (int j = i + 1; j <= len; j++) {
                String subString = s.substring(i, j);
                if (set.contains(subString)) {
                    dp[j] = true;
                }
            }
        }

        // 返回 dp[len]，表示整个字符串 s 是否可以被拆分成一个或多个在 wordDict 中的单词
        return dp[len];
    }
}

状态定义

定义 dp[i] 表示字符串 s 的前 i 个字符 s[0:i-1] 是否可以被拆分成一个或多个在 wordDict 中的单词。

状态转移方程

遍历字符串 s 的每一个位置 i，然后从当前位置 i 开始继续遍历到位置 j，检查 s[i:j] 是否在 wordDict 中。如果在 wordDict 中，并且 dp[i] 为 true，则 dp[j] 也应为 true。

核心思想是通过将问题分解成更小的子问题来解决，并且通过记忆化来避免重复计算。

300. 最长递增子序列 - 力扣（LeetCode）

难度：中等

结合了动态规划和二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 1]; // dp数组用来存储最长上升子序列
        int res = 1; // 记录最长上升子序列的长度
        dp[res] = nums[0]; // 初始化dp数组，将第一个元素放入dp中

        for (int i = 1; i < len; i++) {
            if (dp[res] < nums[i]) {
                dp[++res] = nums[i]; // 如果nums[i]大于dp数组的最后一个元素，直接放入dp数组末尾
            } else {
                int insertIdx = searchInsert(dp, res, nums[i]); // 否则找到合适的位置插入
                dp[insertIdx] = nums[i]; // 插入nums[i]到dp数组中
            }
        }
        return res; // 返回最长上升子序列的长度
    }
    
    // 二分查找插入位置
    private int searchInsert(int[] dp, int res, int target) {
        int left = 1;  // 数组dp是从1开始的
        int right = res;
        while (left <= right) {
            int mid = (left + right) / 2;
            int midVal = dp[mid];
            if (midVal == target) {
                return mid; // 找到target的位置
            } else if (midVal > target) {
                right = mid - 1; // 在左侧继续查找
            } else {
                left = mid + 1; // 在右侧继续查找
            }
        }
        return left; // 返回插入位置
    }
}

代码整体思路是通过维护一个动态规划数组dp，其中dp[i]表示长度为i的最长递增子序列的最后一个元素。然后通过遍历输入数组，使用二分查找来确定每个元素应该插入到dp数组中的位置，从而维持dp数组的递增性质。

最优子结构：对于每个元素nums[i]，通过插入dp数组的位置来维护最长递增子序列的最优解。每次找到的插入位置都是局部最优解，使得整体解也具有最优性。

贪心策略：通过二分查找，将当前元素插入到dp数组中，使得dp数组尽可能保持最长且最小的递增子序列。这是一种贪心策略，确保每一步操作都尽可能优化全局解。

152. 乘积最大子数组 - 力扣（LeetCode）

难度：中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;

        // 以当前元素为最后一个元素的子数组的最小乘积
        int[] min = new int[len];

        // 以当前元素为最后一个元素的子数组的最大乘积
        int[] max = new int[len];

        // 初始化第
        min[0] = nums[0];
        max[0] = nums[0];
        
        int res = max[0];

        // 遍历数组，从第二个元素开始
        for (int i = 1; i < len; i++) {
            // 更新 max 和 min ⭐
            // 
            max[i] = Math.max(Math.max(nums[i], max[i - 1] * nums[i]), min[i - 1] * nums[i]);
            min[i] = Math.min(Math.min(nums[i], max[i - 1] * nums[i]), min[i - 1] * nums[i]);
            // 更新结果
            res = Math.max(max[i], res);
        }

        return res;
    }
}

定义状态

  • max[i]：表示以第 i 个元素结尾的子数组的最大乘积。
  • min[i]：表示以第 i 个元素结尾的子数组的最小乘积。

状态转移方程

  • 以当前元素nums[i]结尾的子数组的最大乘积可能有三种情况：
    • 仅为当前元素 nums[i]
    • 当前元素乘以前一个元素的最大乘积 max[i-1] * nums[i]
    • 当前元素乘以前一个元素的最小乘积 min[i-1] * nums[i] （当前元素是负数时，负数乘负数可能会成为正数）
  • 所以 max[i] = Math.max(nums[i], Math.max(max[i-1] * nums[i], min[i-1] * nums[i]))
  • 最小乘积同理：min[i] = Math.min(nums[i], Math.min(max[i-1] * nums[i], min[i-1] * nums[i]))

416. 分割等和子集 - 力扣（LeetCode）

难度：中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public boolean canPartition(int[] nums){
        int len = nums.length;
        // 前期准备
        if(len<2)return false;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i=0;i<len;i++){
            sum+=nums[i];
            max = Math.max(nums[i],max);
        }
        // 如果元素总和为奇数，那么无法平均分
        if(sum%2==1)return false;
        // 需要在nums中选取若干个元素使得他们的和为target
        int target = sum/2;
        // 如果最大的数大于target，那么任何一个子集和都无法等于target
        if(max>target)return false;
        // 动态规划部分
        // dp[i][j]的意义就是，从下标0...i中选取若干个元素，和为j能否达成
        boolean[][] dp = new boolean[len][target+1];
        // 初始化dp[0][...]
        dp[0][0] = true;
        dp[0][nums[0]] = true;
        for(int i=1;i<len;i++){
            dp[i][0] = true;
            for(int j=1;j<=target;j++){
                // 状态转移方程
                if(j>=nums[i]){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[len-1][target];
    }
}

定义 dp[i][j] 表示是否可以从前 i 个元素中选取若干个元素，使得它们的和等于 j。

初始化 dp[0][0] 为 true，表示不选取任何元素就能得到和为0。

初始化 dp[0][nums[0]] 为 true，表示只选取第一个元素，如果其值等于 nums[0]。

对于每个 i 和 j，更新 dp[i][j] 的值：

  • 如果 nums[i] 大于 j，则不能选择 nums[i]，因此 dp[i][j] = dp[i-1][j]。
  • 如果 nums[i] 小于等于 j，则可以选择 nums[i] 或不选择 nums[i]，因此 dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]。

另一种解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean canPartition(int[] nums) {
        int target = 0;
        
        // 计算数组所有元素的总和
        for (int num : nums) {
            target += num;
        }
        
        // 如果总和是奇数，不能分成两个和相等的子集
        if (target % 2 == 1) return false;
        
        // 目标值为总和的一半
        target /= 2;
        
        // 0-1背包问题的动态规划数组
        int[] f = new int[target + 1];
        
        // 初始化动态规划数组，除了f[0]，其余都设为最小值
        Arrays.fill(f, Integer.MIN_VALUE);
        f[0] = 0;
        
        // 遍历数组中的每个元素
        for (int num : nums) {
            // 倒序遍历，避免重复选择同一个元素
            for (int j = target; j >= num; j--) {
                // 更新f[j]，表示是否可以选择若干个元素使得和等于j
                f[j] = Math.max(f[j], f[j - num] + 1);
            }
        }
        
        // 如果f[target] >= 1，表示可以通过选择若干个元素，使其和等于target
        return f[target] >= 1;
    }
}

动态规划部分：

  • 初始化一个长度为 target + 1 的数组 f，用来存储每个子问题的解。f[j]如果大于0，则表示能够通过选择若干个元素，使其和等于 j。
  • 初始时，将所有元素设为 Integer.MIN_VALUE，表示还未计算的状态。f[0] = 0，表示和为0的情况。

遍历数组和更新状态：

  • 外层循环遍历每个元素 num。
  • 内层循环从 target 开始，倒序遍历到 num，更新 f[j] 的值。
  • 对于每个 j，f[j] = Math.max(f[j], f[j - num] + 1) 表示：若当前和 j 可以通过选择 num 达到，那么我们选择 num 后的状态 f[j - num] + 1 更新 f[j] 的

[P2871 USACO07DEC] Charm Bracelet S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

0-1背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取物品数量 N 和背包容量 V
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        
        int[] volumes = new int[N];
        int[] values = new int[N];
        
        // 读取每件物品的体积和价值
        for (int i = 0; i < N; i++) {
            volumes[i] = scanner.nextInt();
            values[i] = scanner.nextInt();
        }
        
        // 创建动态规划数组
        // dp[i][j]表示从第 1 个到第 i个 物品中选，容量<=j的最大价值
        int[][] dp = new int[N + 1][V + 1];
        
        // 填充动态规划数组
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                int valume = volumes[i-1];
                int val = values[i-1];
                if (j < valume) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - valume] + val);
                }
            }
        }
        
        // 输出最大价值
        System.out.println(dp[N][V]);
        
        scanner.close();
    }
}

我们定义 dp[i][j] 为使用前 i 种物品，且总容量不超过 j 的情况下能够获得的最大价值。

为了构建状态转移方程，我们考虑每种物品是否被包含在当前容量 j 中：

  1. 不选择第 i 种物品： 在这种情况下，最大价值等于只使用前 i-1 种物品时的最大价值，即 dp[i-1][j]。
  2. 选择第 i 种物品： 在这种情况下，我们需要保证背包有足够的容量来容纳第 i 种物品，即 j >= volumes[i-1]。选择第 i 种物品后，背包剩余的容量为 j - volumes[i-1]。此时最大价值等于在剩余容量 j - volumes[i-1] 下使用前几种物品（因为第i种物品只能取一个）可以获得的最大价值 dp[i-1][j - volumes[i-1]] 加上当前物品的价值 vals[i-1]。

由于dp[i-1][...]只被dp[i][...]用到，所以可以将二维数组优化到一维。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取物品数量 N 和背包容量 V
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        
        int[] volumes = new int[N];
        int[] values = new int[N];
        
        // 读取每件物品的体积和价值
        for (int i = 0; i < N; i++) {
            volumes[i] = scanner.nextInt();
            values[i] = scanner.nextInt();
        }
        
        // 动态规划数组
        int[] dp = new int[V + 1];
        
        // 遍历每件物品
        for (int i = 0; i < N; i++) {
            // 倒序遍历背包容量
            for (int j = V; j >= volumes[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - volumes[i]] + values[i]);
            }
        }
        
        // 输出最大价值
        System.out.println(dp[V]);
        
        scanner.close();
    }
}

P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取时间和药的总数
        int V = scanner.nextInt();
        int N = scanner.nextInt();

        int[] costs = new int[N];
        int[] vals = new int[N];

        // 读取每一种草药的时间和价值
        for (int i = 0; i < N; i++) {
            costs[i] = scanner.nextInt();
            vals[i] = scanner.nextInt();
        }

        // 完全背包问题的动态规划解法
        int[][] dp = new int[N + 1][V + 1];
        
        for (int i = 1; i <= N; i++) {
            int cost = costs[i - 1];
            int val = vals[i - 1];
            for (int j = 0; j <= V; j++) {
                if (j >= cost) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - cost] + val);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}

我们定义 dp[i][j] 为使用前 i 种物品，且总容量不超过 j 的情况下能够获得的最大价值。

为了构建状态转移方程，我们考虑每种物品是否被包含在当前容量 j 中：

  1. 不选择第 i 种物品： 在这种情况下，最大价值等于只使用前 i-1 种物品时的最大价值，即 dp[i-1][j]。
  2. 选择第 i 种物品： 在这种情况下，我们需要保证背包有足够的容量来容纳第 i 种物品，即 j >= costs[i-1]。选择第 i 种物品后，背包剩余的容量为 j - costs[i-1]。此时最大价值等于在剩余容量 j - costs[i-1] 下使用所有物品可以获得的最大价值 dp[i][j - costs[i-1]] 加上当前物品的价值 vals[i-1]。

注意和0-1背包的状态转移的区别。

0-1背包：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - valume] + val);

完全背包：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - cost] + val);

同样，也可优化到一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取时间和药的总数
        int V = scanner.nextInt();
        int N = scanner.nextInt();

        int[] costs = new int[N];
        int[] vals = new int[N];

        // 读取每一种草药的时间和价值
        for (int i = 0; i < N; i++) {
            costs[i] = scanner.nextInt();
            vals[i] = scanner.nextInt();
        }

        int[] dp = new int[V + 1];

        for (int i = 1; i <= N; i++) {
            int cost = costs[i - 1];
            int val = vals[i - 1];
            for (int j = cost; j <= V; j++) {  // 正序遍历
                dp[j] = Math.max(dp[j-cost]+val,dp[j]);
            }
        }
        System.out.println(dp[V]);
    }
}

0-1背包：倒序遍历，避免某一个物品被重用

完全背包：正序遍历

32. 最长有效括号 - 力扣（LeetCode）

难度：困难

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        int[] dp = new int[len];  // dp[i] 表示以 s[i] 结尾的最长有效括号的长度
        char[] chars = s.toCharArray();
        int res = 0;  // 记录最长的有效括号长度

        for (int i = 1; i < len; i++) {
            char curChar = chars[i];
            if (curChar == '(') continue;  // 如果当前字符是 '(', 则不能形成有效括号，跳过

            char preChar = chars[i - 1];
            if (preChar == '(') {
                // 如果前一个字符是 '(', 则形成 "()" 模式
                dp[i] = (i - 2 >= 0) ? dp[i - 2] + 2 : 2;  // 计算当前有效括号长度
            } else {
                // 当前字符和前一个字符都是 ')'
                // 需要检查 dp[i-1] 对应的前一个字符是否为 '('
                int keyIndex = i - 1 - dp[i - 1];
                char keyChar = (keyIndex >= 0) ? chars[keyIndex] : ')';
                if (keyChar == ')') continue;  // 如果 keyChar 不是 '(', 跳过
                dp[i] = (keyIndex - 1 >= 0) ? dp[i - 1] + dp[keyIndex - 1] + 2 : dp[i - 1] + 2;  // 更新 dp[i] 值
            }
            res = Math.max(dp[i], res);  // 更新最长有效括号长度
        }
        return res;  // 返回最长有效括号长度
    }
}

状态定义

定义 dp[i] 为以 s[i] 结尾的最长有效括号的长度。

转移方程

我们需要考虑当前字符和前一个字符的组合情况来决定如何更新 dp[i]：

1. 当前字符是 (：

  • 这种情况下，s[i] 不能形成有效括号，所以 dp[i] = 0。

2. 当前字符是 )：

  • 如果前一个字符是 (，即 s[i-1] == '('，它们可以形成一对有效括号 ()
    • 此时，dp[i] = dp[i-2] + 2，其中 dp[i-2] 是 i-2 之前的最长有效括号长度，加上当前的一对有效括号长度 2
  • 如果前一个字符是 )，即 s[i-1] == ')'，我们需要找到与 s[i] 配对的 ( 的位置。
    • 该位置应该是 i - dp[i-1] - 1，即当前 ) 之前的最长有效括号长度的前一个位置。
    • 如果这个位置上的字符是 (，那么 s[i - dp[i-1] - 1] == '('，它们可以形成有效括号。
    • 此时，dp[i] = dp[i-1] + 2 加上之前匹配的部分，即 dp[i] += dp[i - dp[i-1] - 2]（如果这个位置存在）

分别是一下这些情况

1
2
3
4
5
6
7
8
9
10
..(					--> dp[i] = 0

() 					--> dp[i] = 2
...()    			--> dp[i] = dp[i-2]+2

(...))  			--> dp[i] = 0
....)(...))         --> dp[i] = 0

((...))				--> dp[i] = dp[i-1]+2
...((...))			--> dp[i] = dp[i-1]+2+dp[i-1-dp[i-1]-1]

注意边界。

2024-06-18 该篇文章被 jay1an 打上标签: 基础算法 动态规划 归为分类: 基础算法

上一篇：动态规划 - Dynamic Programming - 2 下一篇：贪心算法 - Greedy Algorithm
© 1949-2024 Jay1an
从头努力也坎坷 本站由Hexo驱动｜使用Hexo-theme-A4主题