动态规划--背包问题汇总

刷LeetCode发现有几题很像，参考laluladong的思想整理一下

• 474一和零
• 322零钱兑换 ( 待加入）
• 518 零钱兑换Ⅱ  
• 416分割等和子集
• 1143最长公共子序列

解上面几题的思路都很像，都是“背包问题”，无非就是所要求的目标不太相同。先大概看一下各个题目所求，详细题目参见下文。

474、一和零：给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

　　　　请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

518、零钱兑换Ⅱ ：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

416、分割等和子集：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。转化为：数组中是否有这样的子集使得他们的和，恰好为数组中所有数字和的二分之一，即能否使一个背包容量为数字和/2的背包恰好装满。

1143、最长公共子序列：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

图解：

 

区别：

在背包能够装下当前的物品的情况下：

分割等和子集：

if (j < nums[i-1]):
    dp[i][j] = dp[i - 1][j]
else:
    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i-1]]#能装下

一和零：

if j >= zeros and k >= ones :
    dp[i][j][k] = max( dp[i-1][j][k],dp[i - 1][j - zeros][k - ones] + 1)#能装下
else:
    dp[i][j][k] = dp[i - 1][j][k]

零钱兑换Ⅱ

if(j<coins[i-1]):
    dp[i][j]=dp[i-1][j]
else:
    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]#能装下

最长回文子序列

if(bao[j-1]==things[i-1]):
    dp[i][j]=dp[i-1][j-1]+1#能装
else:
    dp[i][j]=max(dp[i-1][j],dp[i][j-1])

可以看到一个小规律

在背包容量满足当前这个物品的大小时，只有零钱兑换Ⅱ比较特殊，其他的三题都是在  i -1  的基础上进行操作，即本物品之后一个，如果我要装入背包，那么我会在装入之前的 i-1 个物品上进行+1或其他True False操作，而零钱兑换是在没有本物品的基础上+ dp[i][j-coins[i-1]] ，即加上用一张本面额，剩下的金额在包含本面额的面额种类数中的最大组合数，由于题目中已说明每种前有无数个，所以，就算用掉了本面额的钱数，在剩下的金额中还是可以使用本面额，所以是加  i 行，而不是加 i-1行，若每个面额的钱只有一张，那么就是加 i -1行。

不满足当前物品大小时，就比较类似了，都是继承没有该物品时的上一次的值，即 i -1 的值，

题目及代码详情

1143最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

例：

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-subsequence

class Solution(object):
    def  longestCommonSubsequence(self, text1, text2):
        if not text2 or not text1:
            return 0
        bao=text1
        things=text2
        if len(text1)<len(text2):
            bao= text2
            things=text1
        dp= [[0 for _ in range(len(bao)+1)]for _ in range(len(things)+1)]

        for i in range(1,1+len(things)):
            for j in range(1,1+len(bao)):
                if(bao[j-1]==things[i-1]):
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1] 

分割等和子集

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

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200

例：

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum

class Solution(object):
    def canPartition(self, nums):
        n = sum(nums)
        if (n % 2 != 0):
            return False
        else:
            n /= 2
        dp = [[False for i in range(n + 1)] for j in range(len(nums)+1)]
        for t in range(len(nums)):
            dp[t][0] = True
        for i in range(1,len(nums)+1):
            for j in range(1, n + 1):
                if (j - nums[i-1] < 0):
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i-1]]
        return dp[-1][-1]

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

例：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ones-and-zeroes

class Solution(object):
    def findMaxForm(self, strs, m, n):
        dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)]
        for i in range(1, len(strs) + 1):
            ones = strs[i - 1].count("1")
            zeros = strs[i - 1].count("0")
            for j in range(m + 1):
                for k in range(n + 1):
                    if j >= zeros and k >= ones :
                        dp[i][j][k] = max( dp[i-1][j][k],dp[i - 1][j - zeros][k - ones] + 1)
                    else:
                        dp[i][j][k] = dp[i - 1][j][k]
        return dp[-1][-1][-1]

零钱兑换Ⅱ

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

例：

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change-2

python代码

class Solution(object):
    def change(self, m, coins):
        dp = [[0 for _ in range(m + 1)] for _ in range(len(coins) + 1)]
        for i in range(len(coins) + 1):
            dp[i][0] = 1
        for i in range(1, len(coins) + 1):
            for j in range(1, m + 1):
                if(j<coins[i-1]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
        return dp[-1][-1]