2240. 买钢笔和铅笔的方案数 - Kotlin 完全背包问题 求组合方案数

Problem: 2240. 买钢笔和铅笔的方案数

思路

设dp[i]为恰好花费i元能够购买的组合方案数

从背包dp的角度上出发思考这道题，金额money为背包，而价格cost为物品，由于每个物品可以被购买无限次，这道题本质上是一道完全背包求组合方案数的题目

对于背包dp，有外层遍历背包，内层遍历物品和外层遍历物品，内层遍历背包两种遍历方案

• 对于外层遍历背包，内层遍历物品而言，放入物品的顺序是有意义的，按照不同顺序放入相同的物品会被算作多种情况，即排列情况
• 对于外层遍历物品，内层遍历背包而言，放入物品的顺序是无意义的，按照不同顺序放入相同的物品会被算作一种情况，即组合情况

显然，对于这道题，我们需要在外层遍历物品，内层遍历背包，最后输出dp.sum()即为最终结果

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution 
fun Solution.waysToBuyPensPencils(total: Int, cost1: Int, cost2: Int): Long {
    val dp = LongArray(total + 1) { i -> if (i == 0) 1 else 0 }
    val items = intArrayOf(cost1, cost2)
    for (item in items) {
        for (money in 0..total) {
            if (money - item >= 0) {
                dp[money] += dp[money - item]
            }
        }
    }
    return dp.sum()
}