买钢笔和铅笔的方案数【LC2240】
给你一个整数
total，表示你拥有的总钱数。同时给你两个整数cost1和cost2，分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱，去买任意数目的两种笔。请你返回购买钢笔和铅笔的 不同方案数目 。
一眼背包问题 原来数学也可以解决
完全背包
-
思路
问题可以转化为，两种物品重量分别为
cost1和cost2，背包最大容量为total，物品数量不限时，填满不同背包容量时总共方案数-
状态定义： d p [ i ] dp[i] dp[i]为花费 i i i元去买任意数目的两种笔的方案数
-
状态转移
先遍历物品，再遍历背包容量
d p [ i ] + = d p [ i − c o s t [ j ] ] dp[i] += dp[i-cost[j]] dp[i]+=dp[i−cost[j]] -
状态初始化：花费0元时， d p [ 0 ] = 1 dp[0]=1 dp[0]=1
-
-
实现文章来源地址https://www.toymoban.com/news/detail-688186.html
class Solution { public long waysToBuyPensPencils(int total, int cost1, int cost2) { long[] dp = new long[total + 1];// 花费i元去买任意数目的两种笔的方案数 dp[0] = 1L;// 花费0元 // 遍历物品钢笔 for (int i = cost1; i <= total; i += cost1){ dp[i] += dp[i - cost1]; } // 遍历物品铅笔 for (int i = cost2; i <= total; i++){ dp[i] += dp[i - cost2]; } // 遍历记录总共的方案数目 long res = 0L; for (int i = 0; i <= total; i++){ res += dp[i]; } return res; } }- 复杂度
- 时间复杂度： O ( n ) \mathcal{O}(n) O(n)
- 空间复杂度： O ( n ) \mathcal{O}(n) O(n)
- 复杂度
数学
-
思路
枚举可以购买钢笔的数量 i i i，使用剩下的钱 l e f t = t o t a l − i ∗ c o s t 1 left=total - i *cost1 left=total−i∗cost1购买铅笔的最多数量为 j = l e f t / c o s t 2 j=left/cost2 j=left/cost2，那么购买 i i i支钢笔 x ∈ [ 0 , j ] x\in[0,j] x∈[0,j]支铅笔的方案数为 j + 1 j+1 j+1，累加即可得到最中结果文章来源：https://www.toymoban.com/news/detail-688186.html
-
实现
class Solution { public long waysToBuyPensPencils(int total, int cost1, int cost2) { long res = 0L; for (int i = 0; i <= total; i += cost1){ res += (total - i) / cost2 + 1; } return res; } }- 复杂度
- 时间复杂度： O ( n ) \mathcal{O}(n) O(n)
- 空间复杂度： O ( 1 ) \mathcal{O}(1) O(1)
- 复杂度
到了这里，关于【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
