湖州长兴做网站,不写代码做网站,网页微信版官方下载,网站建设手续Day45 动态规划part07 完全背包
70. 爬楼梯#xff08;进阶版#xff09;
卡码网链接#xff1a;57. 爬楼梯#xff08;第八期模拟笔试#xff09; (kamacoder.com)
题意#xff1a;假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 m n)个…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]*(n1)
dp[0] 1
for j in range(1, n1):for i in range(1, m1):if ji: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)]*(amount1)dp[0] 0for i in range(len(coins)):for j in range(coins[i], amount1):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)] * (n1)dp[0] 0for j in range(1, n1):for i in range(1, int(j ** 0.5) 1): #可以优化的if i*ij: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] *(n1)dp[0] Truefor j in range(1, n1):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]
