Miraisen
0%

LeetCode动态规划篇

发表于 更新于 分类于
本文字数： 5.7k 阅读时长 ≈ 5 分钟

本篇为动态规划题单的总结和思路等。

[TOC]

一些基本操作

得到统计数组中每个数字出现次数的数组：

1
2
3
4
int[] all = new int[max+1];
for(int item:nums){
    all[item]++;
}

从记忆化搜索到递归

把递归的计算结果保存下来，那么下次递归到同样的入参时，就直接返回先前保存的结果。

递归搜索+保存计算结果 = 记忆化搜索

对于Python可以用cache装饰器，原理是用Hashmap记录入参和对应的返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 以打家劫舍为例
class Solution:
    def rob(self, nums: List[int]) -> int:
        cache = [-1]*n
        def dfs(i):
            if i < 0:
                return 0
            if cache[i] != -1:
                return cache[i]
           	res = max(dfs(i-1), dfs(i-2)+nums[i])
            cache[i] = res
            return res
        return dfs(n-1)

复杂度计算：用状态个数乘上单个状态所需要的计算时间。

自顶向下算：记忆化搜索；自底向上算：递归。

可以将空间复杂度从O(n)提升到O(1)

1
2
3
4
5
6
7
n = len(nums)
f0 = f1 = 0
for i,x in enumerate(nums):
    new_f = max(f1, f0+x)
    f0 = f1
    f1 = new_f
return f1

416.分割等和子集

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

一开始试图用排序加前缀和判断，但在两个子集相同的情况这种判断不适用。比如 1 2 1 2，是可以分割成两个子集的，但排序后只能分成 1 1 和 2 2。

学习题解：

设nums的元素和是s。要满足两个子集的元素和相等，必须满足：

1、s是偶数 2、子集元素和恰好等于s/2。

所以，首先判断s如果是奇数，直接返回。如果s是偶数，问题转变为了能否从nums中选出一个子序列，其元素和恰好为s/2。

那么这实际上就是0-1背包问题。

0-1背包的子问题：在剩余容量为c时，从前i个物品中得到的最大价值和。

dfs(i,c) = max(dfs(i-1), c), dfs(i-1, c-w[i])+v[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
def zero_one_knapsack(capacity: int, w: List[int], v:List[int]) -> int:
    n = len(w)
    
    #记忆化搜索加装饰器
    @cache
    def dfs(i, c):
        # 先判断边界条件
        if i < 0: # 此时一个物品都没有了
            return 0
        if c < w[i]: # 可选的物品容量大于剩余容量，不予考虑
            return dfs(i-1, c)
        return max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i]) # 否则纳入考虑，选出价值最大的方案
    return dfs(n-1, capacity) # 从最后一个物品开始选，剩余容量就是初始容量

0-1背包的常见变形：

  • 至多装capacity，求方案数/最大价值和
  • 恰好装capacity，求方案数/最大/最小价值和
  • 至少装capacity，求方案数/最小价值和

记忆化搜索的复杂度：状态个数 * 单个状态的计算时间。

记忆化搜索：定义dfs(i,j)表示能否从nums[0]到nums[i]中选出一个和为j的子序列。

1
2
3
4
5
6
7
8
9
10
class solution:
	def canPartition(self, nums:List[int]) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return j == 0
            return j >= nums[i] and dfs(i-1, j- nums[i]) or dfs(i-1, j)
       	
        s = sum(nums)
        return s % 2 == 0 and dfs(len(nums)-1 , s//2)

小F的圣诞礼盒挑战

题目描述

圣诞节到了，小F的妈妈为这个特别的节日准备了许多不同尺寸的圣诞礼盒。小F在玩一个叫做“堆盒子”的游戏，她的妈妈向她发起了一个挑战：尽可能地将盒子堆得更高。每个盒子有特定的长、宽和高，并且堆放时，下面的盒子的每个维度都必须大于放在其上面的盒子。

输入

首先输入一个整数N，代表礼盒的数量。接下来的N行，每行包含三个整数，分别表示一个礼盒的长、宽和高。礼盒的尺寸限制为1到10，礼盒数量不超过1000个。

输出

输出一个整数，表示可以堆出的最高礼盒堆的总高度。

样例

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
输入：
4
1 1 1
2 3 4
3 6 7
4 5 6

输出：
12

提示：
在这个例子中，最佳的堆叠方式是选择第一、第二和第三个盒子，因为它们的尺寸条件允许按照这样的顺序堆叠。每个盒子的高度分别为4、7和1，总高度达到12。

输入：
4
1 1 1
1 1 1
2 2 2
2 2 2

输出：
3

提示：
一种有效的选择是堆叠第一个和第三个盒子，它们的高度总和为3，这是该情况下可能达到的最高高度。

解析

三维动态规划。首先将所有礼盒按照顺序进行排序。令f[i]表示以第i个礼盒为底时，所能达到的最高的高度。

一开始有f[i]=a[i][2]，这是因为所有礼盒都可以上面不放礼盒。

对于j<i，如果a[j][0] < a[i][0], a[j][1] < a[i][1], a[j][2] < a[i][2]，那么说明礼盒j可以放在礼盒i上面，因此f[i]的其中一个决策为f[j] + a[i][2]。在这些决策中，取一个最大值即可。

最终，f的最大值即为结果。

部分核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
ls = [] # 用于存储所有盒子的尺寸

for i in range(n):
    ls.append(list(map(int,input().split())))
ls.sort()

f = [0 for _ in range(n)]
for i in range(n):
    f[i] = ls[i][2]
    for j in range(i):
        if all(x < y for x,y in zip(ls[j], ls[i])):
            f[i] = max(f[i], f[j] + ls[i][2])

3290.最高乘法得分

给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。

你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。你的得分将是 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3] 的值。

返回你能够获得的 最大 得分。

示例 1：

输入： a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]

输出： 26

解释：
选择下标 0, 1, 2 和 5。得分为 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26。

示例 2：

输入： a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]

输出： -1

解释：
选择下标 0, 1, 3 和 4。得分为 (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1。

提示：

  • a.length == 4
  • 4 <= b.length <= 105
  • -105 <= a[i], b[i] <= 105

解析

从b中选一个长为4的子序列。定义dfs(i, j)表示从b[0]到b[i]中选出j+1个数，来和a[0]到a[j]算一个点积的最大值。考虑b[i]选或不选

  • 不选：dfs(i-1, j)
  • 选：dfs(i-1,j-1) + a[j]*b[i]

dfs(i, j) = max(dfs(i-1, j), dfs(i-1, j-1) + a[j]*b[i])

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxScore(self, a:List[int], b: List[int])->int:
        @cache # 缓存装饰器，避免重复计算dfs的结果（记忆化）
        def dfs(i:int, j:int) -> int:
            if j < 0: # 数字匹配完了
                return 0
            if i < 0: # 此时j>=0
                # 还有数字未匹配，不合法
                return -inf
        	return max(dfs(i-1, j), dfs(i-1,j-1) + a[j] * b[i])
       	return dfs(len(b)-1, 3) # 注意是下标哈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    public long maxScore(int[] a, int[] b){
        int n = b.length;
        long[][] memo = new long[n][4];
        for(long[] row: memo){
            Arrays.fill(row, Long.MIN_VALUE);//没有计算过
        }
        return dfs(n-1, 3, a, b, memo);
    }
    
    private long dfs(int i, int j, int[] a, int[] b, long[][ ] memo){
        if(j<0) return 0; // 选完了
        if(i<0) return Long.MIN_VALUE / 2;//没选完   防止溢出
        if(memo[i][j] == Long.MIN_VALUE)//需要计算，并记忆化
        {
            memo[i][j] = Math.max(dfs(i-1, j, a, b, memo), dfs(i-1, j-1, a, b, memo) + (long) a[j] * b[i]);
        }
        return memo[i][j];
    }
}

2266. 统计打字方案数

Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。

img

为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。

  • 比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母 'k' 。
  • 注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。

但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。

  • 比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。

给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。

由于答案可能很大，将它对 109 + 7 取余 后返回。

示例 1：

1
2
3
4
5
6
输入：pressedKeys = "22233"
输出：8
解释：
Alice 可能发出的文字信息包括：
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。
由于总共有 8 种可能的信息，所以我们返回 8 。

示例 2：

1
2
3
4
5
输入：pressedKeys = "222222222222222222222222222222222222"
输出：82876089
解释：
总共有 2082876103 种 Alice 可能发出的文字信息。
由于我们需要将答案对 10^9 + 7 取余，所以我们返回 2082876103 % (109 + 7) = 82876089 。

解析

把相同字符视为一组，在一组内处理；

定义f[i]或g[i]表示长为i的只有一种字符的字符串对应的文字信息种类数

对于字符不为7或9的情况，定义f[i]表示长为i的只有一种字符的字符串对应的文字信息种类数；转移方程：

f[i] = f[i-1] + f[i-2] + f[i-3]

对于字符为7或9的情况，转移方程

g[i] = g[i-1] + g[i-2] + g[i-3] + g[i-4]。

不同组之间互不影响，根据乘法原理把不同组的文字信息种类数相乘得到答案。

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{
    private static final int MOD = 1_000_000_007;
    private static final int MX = 100_001;
    private static final long[] f = new long[MX];
    private static final long[] g = new long[MX];
    
    static{
        f[0] = g[0] = 1;
        f[1] = g[1] = 1;
        f[2] = g[2] = 2;
        f[3] = g[3] = 4;
        for(int i = 4;i<MX;i++){
            f[i] = (f[i-1] + f[i-2] + f[i-3]) % MOD;
            g[i] = (g[i-1] + g[i-2] + g[i-3] + g[i-4]) % MOD;
        }
    public int countTexts(String s){
        long ans = 1;
        int cnt = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            cnt++;
            if(i == s.length() - 1 || c != s.charAt(i+1)){
                ans = ans * (c!='7'&&c!='9'?f[cnt]:g[cnt])%MOD;
                cnt = 0;
            }
        }
        return (int)ans;
    }
    }

复习题单

题号 名字 状态
3290 最高乘法得分 接近独立写出
377 组合总和Ⅳ 不能独立写出
2266 统计打字方案数 有算法思路但是不知道如何java实现
192 打家劫舍 过了
740 删除并获得点数 不会
2320 统计放置房子的方式数 有思路还没过
53 最大子数组和 过了🥳