夜周赛76【20220416】

https://leetcode-cn.com/problems/number-of-ways-to-buy-pens-and-pencils/

请问这里加一是因为向下取整还是因为只买钢笔或者只买铅笔也算是一种方案呢？

  1. class Solution:
  2.     def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
  3.         """
  4.         T: O(n)
  5.         S: O(1)
  6.         idea: 翻硬币，两个变量转换为一个变量的变化
  7.         """
  8.         amount_cost1 = total // cost1
  9.         res = 0
  10.         for i in range(amount_cost1+1):
  11.             remainder = total - i * cost1
  12.             # 在余数范围内均可以购买
  13.             res += remainder // cost2 + 1
  14.         return res

其他解法

https://oi-wiki.org/math/number-theory/euclidean/#_1

找零问题的类推 —- DP
https://leetcode-cn.com/problems/number-of-ways-to-buy-pens-and-pencils/comments/1510665
https://leetcode-cn.com/problems/coin-change/