大礼包(LC638)
哪些公司问过
答案要点
- 状态为剩余需求向量,返回最小花费
- 初始答案为全部按单价购买
- 礼包任一物品超过需求则不可用,否则递归剩余需求加礼包价
- 哈希表缓存需求向量的结果,避免重复计算
- 预处理剔除不划算的礼包,减少分支
易错点
- 允许礼包导致购买数量超过需求
- 忘记和全部单买的方案比较
- 不做记忆化,状态大量重复导致超时
面试官常见追问
- 需求向量怎么作为哈希表的键?
- 能用完全背包的方式做吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场