动态规划(DP)专题训练

复习一下动态规划的内容，回顾一部分经典题型

1.学习资源

残酷刷题群算法小讲座：动态规划的套路 by wisdompeak - Youtube
视频里的Slide - Google docs
动态规划题目列表 - Leetcode
背包问题

2.简单的解题思路

对于一些比较常规的题目，可以采用如下策略：

  1. 定义dp[i][j]：表示第i-th轮的第j种状态 (j=1,2,…,K)
  2. 千方百计将dp[i][j]与前一轮的状态dp[i-1][j]产生关系(j=1,2,…,K)
  3. 最终的结果是dp[last][j]中的某种aggregation (sum, max, min …)

3.递推类型

3.1. 爬楼梯

因为每次只能爬1个或2个，因此套用上方的解决方法：

  1. 定义dp[i]表示到i的数量
  2. dp[i] = dp[i-1] + dp[i-2]即可以通过跨一节(从i-1)或跨过两节(从i-2)到达i处
  3. 最终的结果是dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = []
    for(let i = 0;i <= n;i++) {
        dp.push(0)
    }
    dp[0] = 1
    dp[1] = 1
    for(let i = 2;i <= n;i++) dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
};

3.2. 分隔数组以得到最大和

2023-04-19每日一题

  1. 定义dp[i]表示到下标i的最大答案
  2. dp[i]=max(dp[i−1]+val[i−1]∗1,dp[i−2]+val[i−2]∗2,...)dp[i] = max(dp[i-1]+val[i-1]*1, dp[i-2]+val[i-2]*2,...)是状态转移方程，可以最多转移k个
  3. 最终的结果是dp[n]

dp：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * (len(arr)+1)
        for i,v in enumerate(arr):
            mx = 0
            for j in range(k):
                if i - j>= 0:
                    mx = max(mx, arr[i-j])
                    dp[i+1] = max(dp[i+1], dp[i-j] + (j+1)*mx)
        return max(dp)

记忆化搜索：
待填

3.3 使数组严格递增

2023-04-20每日一题
状态转移：无非两种，换或者不换，找当前状态下最小即可

记忆化搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
INF = 0x7FFFFFFF

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        ordered = sorted(set(arr2))
        @lru_cache(None)
        def dfs(pos:int, pre:int):
            if pos >= len(arr1):
                return 0
            nxt = bisect.bisect_right(ordered, pre)
            return min(
                1 + dfs(pos+1, ordered[nxt]) if nxt < len(ordered) else INF, # swap
                dfs(pos+1, arr1[pos]) if pre < arr1[pos] else INF # not swap
            )
        return -1 if dfs(0, -INF) >= INF else dfs(0, -INF)

dp：
待填

4.背包问题

泛指一类「给定价值与成本」，同时「限定决策规则」，在这样的条件下，如何实现价值最大化的问题。

4.1. 01背包问题

「01背包」是指：

  • 给定物品价值与体积（对应了「给定价值与成本」）
  • 在规定容量下（对应了「限定决策规则」）
  • 如何使得所选物品的总价值最大。
    只要任何问题能够转化为具有该三点条件的问题，那么就可以当作01背包问题

416. 分割等和子集

该问题可以转化为

  • 给定每个物品的价值（数组中每一个数的值）
  • 在规定容量下（总和/2）
  • 对于每一个数，可以选或不选，能满足规定容量即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canPartition(vector<int>& nums) {
         int sum = accumulate(nums.begin(), nums.end(), 0);
         int mx = *max_element(nums.begin(), nums.end());
         int target = sum / 2;
         if(mx > target) return false;
         if(sum & 1) return false;
         int n = nums.size();
         vector<vector<bool>> dp(n+1, vector<bool>(target + 1, 0));
         dp[0][nums[0]] = true;
         for(int i = 1;i < n;i++) {
             int x = nums[i];
             dp[i][0] = true;
             for(int j = 0;j <= target;j++) {
                 if(j-x>0) dp[i][j] = dp[i-1][j]|dp[i-1][j-x];
                 else dp[i][j] = dp[i][j] | dp[i-1][j];
             }
         }
         
         return dp[n-1][target];
    }
};

优化一下，优化到二维空间

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
class Solution {
public:
    bool canPartition(vector<int>& nums) {
         int sum = accumulate(nums.begin(), nums.end(), 0);
         int mx = *max_element(nums.begin(), nums.end());
         int target = sum / 2;
         if(mx > target) return false;
         if(sum & 1) return false;
         int n = nums.size();
         vector<vector<bool>> dp(2, vector<bool>(target + 1, 0));
         dp[0][nums[0]] = true;
         for(int i = 1;i < n;i++) {
             int now = i&1;
             int last = (i+1)&1;
             int x = nums[i];
             dp[now][0] = true;
             for(int j = 0;j <= target;j++) {
                 if(j-x>0) dp[now][j] = dp[last][j]|dp[last][j-x];
                 else dp[now][j] = dp[last][j];
             }
         }
         
         return dp[0][target]|dp[1][target];
    }
};

再优化到一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canPartition(vector<int>& nums) {
         int sum = accumulate(nums.begin(), nums.end(), 0);
         int mx = *max_element(nums.begin(), nums.end());
         int target = sum / 2;
         if(mx > target) return false;
         if(sum & 1) return false;
         int n = nums.size();
         vector<bool> dp(target+1,0);
         dp[nums[0]] = true;
         for(int i = 1;i < n;i++) {
             int x = nums[i];
             dp[0] = true;
             for(int j = target;j >= 0;j--) {
                 if(j-x>0) dp[j] = dp[j]|dp[j-x];
                 else dp[j] = dp[j];
             }
         }
         return dp[target];
    }
};

494. 目标和

该问题可以转化为

  • 给定每个物品的价值（+n或者-n选一个）
  • 在规定容量下（到target大小）
  • 最后得到最多能够到达的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<vector<int>> dp(nums.size(),vector<int>(4000,0));
        int offset = 2000;
        dp[0][offset+nums[0]] += 1;
        dp[0][offset-nums[0]] += 1;
        for(int i = 1;i < nums.size();i++) {
            int num = nums[i];
            int now = i;
            int last = i-1;
            for(int i = 0;i < 4000;i++) {
                if(i-num >= 0) dp[now][i] += dp[last][i-num];
                if(i+num < 4000) dp[now][i] += dp[last][i+num];
            }
        }
        return dp[nums.size()-1][target+offset];
    }
};

474. 一和零

该问题可以转化为

  • 给定每个物品的价值（0的个数和1的个数）
  • 在规定容量下（到m个0和n个1以下）
  • 最多能够包含的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i = 0;i < strs.size();i++){
            string now = strs[i];
            int c1=0,c2=0;
            for(auto i : now){
                if(i=='0') c1++;
                else if(i=='1') c2++;
            }
            for(int j = m;j >= c1;j--) {
                for(int k = n;k >= c2;k--) {
                            dp[j][k] = max(dp[j][k],dp[j-c1][k-c2]+1); 
                }
            }
        }
        return dp[m][n];
    }
};

4.2. 完全背包问题

「完全背包」是指：

  • 给定物品价值与体积（对应了「给定价值与成本」），且物品可以无限次选
  • 在规定容量下（对应了「限定决策规则」）
  • 如何使得所选物品的总价值最大。

完全背包问题与01背包问题的区别就是可以无限选，因此在内层递推遍历时可以采用正序遍历，因此可以表示多种状态
先来点套路+暴论

背包问题技巧：
1.如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；

1
2
for num in nums:
   for i in range(target, nums-1, -1):

2.如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
1
2
for num in nums:
   for i in range(nums, target+1):

3.如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
1
2
for i in range(1, target+1):
   for num in nums:

139 单词拆分（medium）

377.组合总和 Ⅳ

该题中明确说明是找排列数，需要把待选列表放到外层遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long long> dp(target+1,0);
        for(auto j : nums){
            if(j <= target) dp[j] += 1;
        }
        for(int i = 0;i <= target;i++){
            for(auto j : nums) {
                if(i-j>=0) dp[i] += dp[i-j];
            }
        }
        for(auto i : dp) cout << i << " ";
        return dp[target];
    }
};

279.完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numSquares(int n) {
        vector<int> nums;
        int now = 2;
        while(1) {
            int tmp = pow(now,2);
            if(tmp > 10000) break;
            nums.push_back(tmp);
            now++;
        }
        vector<int> dp(n+1,0);
        for(int i = 0;i <= n;i++) {
            dp[i] = i;
        }
        for(auto i:nums) {
            for(int j = i;j <= n;j++) {
                dp[j] = min(dp[j],dp[j-i]+1);
            }
        }
        return dp[n];
    }
};

518.零钱兑换 II

该问题和上方的爬楼梯 非常相似，无非是爬楼梯一次只能爬1节or2节，而本问题可以一次使用所给面值

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0] = 1;
        for(auto x:coins) {
            for(int j = x;j <= amount;j++) {
                dp[j] += dp[j-x];
            }
        }
        return dp[amount];
    }
};

322.零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int sz = coins.size();
        vector<int> dp(amount+1,9999999);
        dp[0] = 0;
        for(auto x : coins){
            if(x <= amount) dp[x] = min(dp[x],1);
            for(int j = x+1;j <= amount;j++){
                if((dp[j]<9999999||dp[j-x]<9999999))dp[j] = min(dp[j],dp[j-x]+1);
            }
        }
        if(dp[amount]==9999999) return -1;
        return dp[amount];
    }
};

4.3. 多重背包

多重背包是指，在01背包的基础上，每个物品可以选有限次。

4.4. 混合背包

4.5. 分组背包

4.6. 多维背包

4.7. 树形背包

4.8. 背包方案数

4.9. 背包具体方案

4.10. 泛化背包

5. 状态压缩

6. 子序列动态规划问题

要把握状态是如何转移的，比如说以下题目

940. 不同的子序列 II

题目是通过以前的状态转移过来的，因此可以简化为用dp表示以x结尾的子序列的个数

1
2
3
4
5
6
7
8
class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        dp = [0] * 27
        for i in s:
            n = ord(i) - ord('a')
            dp[n] = (1 + sum(dp)) % mod
        return sum(dp) % mod

1349. 参加考试的最大学生数

1434. 每个人戴不同帽子的方案数

691. 贴纸拼词

专题训练
#算法 #动态规划 #未完成
动态规划(DP)专题训练
https://tech.jasonczc.cn/2023/algorithm/train-dp/
作者
CZY
发布于
2023年4月20日
许可协议