每天一道leetcode(Day 27)

面试题 08.11. 硬币

题目描述

硬币。给定数量不限的硬币，币值为 25 分、10 分、5 分和 1 分，编写代码计算 n 分有几种表示法。(结果可能会很大，你需要将结果模上 1000000007)

示例

• 示例 1:

输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

• 示例 2:

输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明：

注意:

你可以假设：

0 <= n (总金额) <= 1000000

解题思路

动态规划：

• 建立状态矩阵 dp，dp[i]表示组成 i 元钱一共有多少种方式，其中将每一项都初始化为 1 是全部由 1 元钱组成的情况；
• 状态转移矩阵：dp[j] = (dp[j] + dp[j - coin[i]]) % (1e9 + 7)，i 元钱的组成方式可以由 i-5，i-10，i-25 这几种情况的组成方式加起来得到，这里不用考虑 i-1，因为我们初始化将每一项置为 1 考虑的就是这种情况；
• 得到最终结果 dp[n]

注意：
内外循环的顺序不能颠倒，如果外层是钱的数量的循环的话，会包括一些重复情况，例如：当 n=10 的时候，会将 1+1+1+1+1+5、5+1+1+1+1+1 算作是不同的情况从而会使结果不准确

代码

/**
 * @param {number} n
 * @return {number}
 */
var waysToChange = function (n) {
  const coin = [1, 5, 10, 25];
  let dp = new Array(n + 1).fill(1);
  for (let i = 1; i < 4; i++) {
    for (let j = 1; j <= n; j++) {
      if (j - coin[i] >= 0) {
        dp[j] = (dp[j] + dp[j - coin[i]]) % (1e9 + 7);
      }
    }
  }
  return dp[n];
};

参考

面试题 08.11. 硬币