买钢笔和铅笔的方案数【LC2240】
给你一个整数
total，表示你拥有的总钱数。同时给你两个整数cost1和cost2，分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱，去买任意数目的两种笔。请你返回购买钢笔和铅笔的 不同方案数目 。
一眼背包问题 原来数学也可以解决
完全背包
- 思路
问题可以转化为，两种物品重量分别为cost1和cost2，背包最大容量为total，物品数量不限时，填满不同背包容量时总共方案数
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; } }
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; } }
