上一主题 下一主题
ScriptCat,新一代的脚本管理器脚本站,与全世界分享你的用户脚本油猴脚本开发指南教程目录
返回列表 发新帖

518. 零钱兑换 II - 从缓存到二维dp到一维dp

[复制链接]
  • TA的每日心情
    擦汗
    2024-7-16 09:20
  • 签到天数: 192 天

    [LV.7]常住居民III

    701

    主题

    5787

    回帖

    6623

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6623

    荣誉开发者管理员油中2周年生态建设者喜迎中秋

    发表于 2024-9-27 16:55:41 | 显示全部楼层 | 阅读模式

    https://leetcode.cn/problems/coin-change-ii/description/

    首先我们可以设计一个缓存

    假设到了某一个数字,如果当前数字已经小于了金额,则跳过该数字

    如果当前数字大于金额,则存在两种可能

    1.放弃该数字,继续往前走

    2.挑选一个数字,然后扣减金额,继续在该数字上停留

    则可以写出

    var change = function (amount, coins) {
        const cache = new Map()
        const dfs = (amount, pos) => {
            if (amount == 0) {
                return 1
            }
            if (amount < 0) {
                return 0
            }
            if (pos >= coins.length) {
                return 0
            }
            const flag = `${amount} ${pos}`
            if (cache.has(flag)) {
                return cache.get(flag)
            }
            let result = undefined
            if (amount < coins[pos]) {
                result = dfs(amount, pos + 1)
            } else {
                result = dfs(amount, pos + 1) + dfs(amount - coins[pos], pos)
            }
            cache.set(flag, result)
            return result
        }
        return dfs(amount, 0)
    };

    那我们现在开始转成动态规划,有两维,一维是金额,一维是硬币,边界时金额为0时则存在一种,同时为了防止边界溢出我们要稍加一点数组

    var change = function (amount, coins) {
        const dp = new Array(coins.length + 1).fill(0).map(() => new Array(amount + 1).fill(0))
        for (let index = 0; index < dp.length; index++) {
            dp[index][0] = 1
        }
        for (let index = dp.length - 2; index >= 0; index--) {
            for (let mount = 1; mount <= amount; mount++) {
                if (mount < coins[index]) {
                    dp[index][mount] = dp[index + 1][mount]
                } else {
                    dp[index][mount] = dp[index + 1][mount] + dp[index][mount - coins[index]]
                }
            }
        }
        return dp[0].pop()
    };

    到这里我们可以看到,每一维度仅与上一层和本层金额稍少的位置

    那就可以将二维转化成一维,一层一层往上递归,同时又可以发现

    我们对硬币从前往后递归和从后往前递归都无所谓

    因为每次递归的时候只考虑该层之前的层数存在的可能数

    无论硬币数是[1,2,5]还是[5,2,1]都不会影响答案

    那我们可以写出

    const change = function (amount, coins) {
        const dp = Array(amount + 1).fill(0)
        dp[0] = 1
        for (const coin of coins) {
            for (let mount = 1; mount <= amount; mount++) {
                dp[mount] = dp[mount] + (mount < coin ? 0 : dp[mount - coin])
            }
        }
        return dp.pop()
    }

    将边界略微精简即可得到官解的答案

    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
  • TA的每日心情
    开心
    2024-3-13 10:14
  • 签到天数: 211 天

    [LV.7]常住居民III

    301

    主题

    4109

    回帖

    3990

    积分

    管理员

    积分
    3990

    管理员荣誉开发者油中2周年生态建设者喜迎中秋油中3周年挑战者 lv2

    发表于 2024-9-29 09:48:47 | 显示全部楼层

    上不慕古,下不肖俗。为疏为懒,不敢为狂。为拙为愚,不敢为恶。/ 微信公众号:一之哥哥
    回复

    使用道具 举报

    发表回复

    本版积分规则

    快速回复 返回顶部 返回列表