Day45 动态规划part07 完全背包
70. 爬楼梯（进阶版）
卡码网链接：57. 爬楼梯（第八期模拟笔试） (kamacoder.com)
题意：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
这道题出现的问题：（1）首先dp[0]的初始化还应该是1，因为dp[0]是后序累加的基础；（2）递推公式没有想清楚，这里是dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]，所以是累加的关系
n,m = map(int, input().split())
dp = [0]*(n+1)
dp[0] = 1
for j in range(1, n+1):
for i in range(1, m+1):
if j>=i:
dp[j] += dp[j-i]
print(dp[-1])
322. 零钱兑换
leetcode链接：322. 零钱兑换 - 力扣（LeetCode）
题意：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。
思路：题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。
动规五部曲：
- dp数组含义：dp[i]表示金额数位i时，最少需要的硬币个数
- 递推公式：dp[j] = min(dp[j], dp[j - coins[i]]+1)
- 初始化：dp数组应该为inf，因为求的时最小的；dp[0]表示总金额为0时需要的硬币数量应该为0
- 遍历顺序：这道题组合和排列都没关系，因为不管哪种都能求到结果
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')]*(amount+1)
dp[0] = 0
for i in range(len(coins)):
for j in range(coins[i], amount+1):
dp[j] = min(dp[j], dp[j-coins[i]]+1)
print(dp)
if dp[amount] == float('inf'):
return -1
return dp[amount]
279.完全平方数
leetcode题目链接：279. 完全平方数 - 力扣（LeetCode）
题意：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
思路：把题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？和上一题的思路是一致的
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] * (n+1)
dp[0] = 0
for j in range(1, n+1):
for i in range(1, int(j ** 0.5) + 1): #可以优化的
if i*i<=j:
dp[j] = min(dp[j], dp[j-i*i]+1)
# print(dp)
return dp[n]
139.单词拆分
leetcode链接：139. 单词拆分 - 力扣（LeetCode）
题意：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
示例 2：
- 输入: s = "applepenapple", wordDict = ["apple", "pen"]
- 输出: true
- 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
- 注意你可以重复使用字典中的单词。
思路：这道题中wordDict是可以使用多次的，所以是一个完全背包问题
动规五部曲：
- dp数组表示：dp[i]表示第i个位置是否可以被拆分，用bool类型
- 递推公式：dp[j] = dp[j-wordDict[i]] and (dp[j-wordDict[i] : j] in wordDict)。如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
- 初始化：dp数组初始化为false。dp[0]表示如果字符串为空的话，说明出现在字典里。但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。
- 遍历顺序：这一是个排列数，因为要强调顺序。"apple", "pen" 是物品，那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。所以说，本题一定是 先遍历 背包，再遍历物品。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] *(n+1)
dp[0] = True
for j in range(1, n+1):
for word in wordDict:
if len(word) <= j:
if s[j-len(word):j] ==word and dp[j-len(word)] == True:
dp[j] = True
print(dp)
return dp[n]
