[leetcode刷题笔记]动态规划之背包问题

当然拿到问题后，需要做到以下几个步骤：
1.分析是否为背包问题。
2.是三种背包问题中的哪一种。
3.是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
4.如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。

三种背包问题

组合问题公式

dp[i] += dp[i-num]

True、False问题公式

dp[i] = dp[i] or dp[i-num]

最大最小问题公式

dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)

以上三组公式是解决对应问题的核心公式。

背包问题的判定

背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。

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

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

2.如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。

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

3.如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。

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

以上内容来自希望用一种规律搞定背包问题---Jackie1995，下面介绍一些例题。

0-1背包问题

给定 $n$ 种物品和一个背包，物品 $i$ 的重量是 $W_i$ ,其价值为 $V_i$ ,背包的容量为 $c$ 。问应该如何选择装入背包的物品使得装入背包中的物品总价值最大？

在选择装入背包的物品时，对每种物品 $i$ 只有两种选择，即装入背包或者不装入背包。不能将物品 $i$ 装入背包多次，也不能只装入部分的物品i。

[分析] $dp [i, v]$ 表示前 $i$ 件物品恰放入一个容量为 $v$ 的背包可以获得
的最大价值。
（1）当 $C=0$ 时， $dp[0]=0$
（2）当 $C>0$ 时，每个物品都有0-1两种状态，则其状态转移方程便是:

$dp [i, v] = \max\{dp [i − 1, v], dp [i − 1, v − C_i ] + W_i \}$

[凑硬币问题]

有1元，2元，5元硬币若干，凑到20元最少需要多少枚硬币。

(1) $n=0$ 时，需要0个硬币， $dp[0]=0$
(2) $n>0$ 时，考虑最后一次硬币硬币情况，向前分析，即可得状态转移方程:

$\operatorname{dp}[n]=\min \{1+d p[n-1], 1+d p[n-2], 1+d p[n-5]\}$

def detectMinCoins(M,coins):
    dp = [0]*(M+1)
    for N in range(1,M+1):
        l = []
        for i in coins:
            if N>=i:
                l.append(dp[N-i]+1)
        dp[N] = min(l)
    return dp[M]

硬币问题

给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

[分析]
dp[i][j] 使用前i种硬币计算j分的表示法种数令coins=[25, 10, 5, 1]

dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i]] + dp[i-1][j-2*coins[i]] + ... dp[i-1][j-k*coins[i]]
j >= k*coins[i]
dp[i][j-coins[i]] = dp[i-1][j-coins[i]] + dp[i-1][j-2*coins[i]] + ... dp[i-1][j-k*coins[i]]
dp[i][j] - dp[i][j-coins[i]] = dp[i-1][j]
dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j]

举个例子，当n=10时

coin\n	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1	1	1
5	1	1	1	1	1	2	2	2	2	2	3
10	1	1	1	1	1	2	2	2	2	2	4
25	1	1	1	1	1	2	2	2	2	2	4

简化问题，只需要得出最后一行即可。

def detectMinCoins(M,coins):
    coins = [1, 5, 10, 25]
    dp = [0] * (M + 1) 
    dp[0] = 1
    for coin in coins :
        for i in range(coin, M + 1) :
            dp[i] = (dp[i] + dp[i - coin])
    return dp[M]

打家劫舍问题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

[分析]状态转移方程
数组个数length，当length=0时，返回0
当length=1时，dp[0]=nums[0]
当length=2时，dp[1]=max(nums[0],nums[1])
当length=3时，dp[i]=max(dp[i-2]+nums[i],dp[i-1])

class Solution:
    def rob(self, nums: List[int]) -> int:
        length = len(nums)
        if length == 0:
            return 0
        dp = [0]*length
        dp[0]=nums[0]
        if length > 1:
            dp[1] = max(nums[0],nums[1])
        if length > 2:
            for i in range(2,length):
                dp[i] = max(dp[i-2]+nums[i],dp[i-1])
        return dp[-1]

目标和

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

sum(P) 前面符号为+的集合；sum(N) 前面符号为减号的集合，所以题目可以转化为

$sum(P) - sum(N) = target \\ sum(nums) + sum(P) - sum(N) = target + sum(nums)\\ 2 * sum(P) = target + sum(nums) \\ sum(P) = (target + sum(nums)) / 2$

因此题目转化为01背包，也就是能组合成容量为sum(P)的方式有多少种

class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        w = (sum(nums) + S) // 2

        if sum(nums) < S or (sum(nums) + S) % 2 == 1:
            return 0

        dp = [0] * (w+1)
        dp[0] = 1
        for num in nums:
            j = w 
            while j >= num:
                dp[j] += dp[j - num]
                j -= 1
    
        return dp[w]

组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

排列组合问题首先想到贪心问题，但这道题是明显的动态规划问题，类似于上文中硬币问题。但与硬币不同的是，顺序不同的序列被视作不同的组合。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
            dp = [0] * (target + 1) 
            dp[0] = 1
            for i in range(target + 1) :
                for num in nums :
                   if i >= num:
                        dp[i] += dp[i - num]
            return dp[-1]

reference

希望用一种规律搞定背包问题---Jackie1995

题目来源：力扣LeetCode,著作权归领扣网络所有。

coin\n	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1	1	1
5	1	1	1	1	1	2	2	2	2	2	3
10	1	1	1	1	1	2	2	2	2	2	4
25	1	1	1	1	1	2	2	2	2	2	4

coin\n	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1	1	1
5	1	1	1	1	1	2	2	2	2	2	3
10	1	1	1	1	1	2	2	2	2	2	4
25	1	1	1	1	1	2	2	2	2	2	4

coin\n	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1	1	1
5	1	1	1	1	1	2	2	2	2	2	3
10	1	1	1	1	1	2	2	2	2	2	4
25	1	1	1	1	1	2	2	2	2	2	4