Day45代码随想录动态规划part07：70. 爬楼梯（进阶版）、322. 零钱兑换、279.完全平方数、139.单词拆分

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] = 0for 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 -1return 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] = 0for 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] = Truefor 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] = Trueprint(dp)return dp[n]