【刷题DAY44】518, 337.md

发表于 | 分类于

518. 零钱兑换 II

题目链接：https://leetcode.cn/problems/last-stone-weight-ii/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • dp[j]：凑成总金额j的货币组合数为dp[j]
  • 求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]
  • dp[0] = 1
  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包

0x5 今日收获，记录一下自己的学习时长

  • 1h

337. 组合总和 Ⅳ

题目链接：https://leetcode.cn/problems/combination-sum-iv/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • dp[i]: 凑成目标正整数为i的排列个数为dp[i]
  • 求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]]
  • dp[0] = 1
  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品

0x5 今日收获，记录一下自己的学习时长

  • 1h

总结

  • 完全背包
    • 每件物品可以无限次放进背包
      • 一维滚动数据 里层for循环需要从小到大进行遍历，为了多次放同一个物品
    • for循环先遍历物品或者先遍历容量都是可以的
    • 求组合数
      • 遍历只能先物品再容量
    • 求排列数据
      • 遍历只能先容量再物品

复习

  • day18
    • 路径总和ii
    • 从前序与中序遍历序列构造二叉树:

待重点复习

518, 337