面试题 08.11. 硬币[medium]
面试题 08.11. 硬币[medium]
https://leetcode-cn.com/problems/coin-lcci/
硬币。给定数量不限的硬币，币值为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
通过次数18,220 | 提交次数36,157
f**k 背包问题
2020-06-12
- 对于动态规划，一直无法理解的是选择前i个元素所谓遍历。前i个元素 vs 第1个元素vs第i+2个元素，什么时候能够把后者包括在内？在前i+2个元素的时候，真的能够覆盖这个选择吗？f**k!!!
- 从起点开始，怎么就能推到所有状态，不会导致有些状态被跳过去了吗？
- dp[i][j]到底是dp[i][x==j]还是dp[i][x<=j]，我理解的一直都是后一种，但看到有些案例需要使用max(dp[i][0...j])来计算。
题解理解所有
2020-06-12
https://leetcode-cn.com/problems/coin-lcci/solution/ying-bi-by-leetcode-solution/
看各种解释和视频都理解不了，按照这题解一步步优化下去，终于掌握了思路，心理终于有些安定。目前不太确定的是第一个问题：前i个元素选择，如何保证1和k+2以后也被包括在内？其他内容没有多大问题了，不过仍然不知道别人是怎么一步到位的，遇到新的问题我估计还是得一步步往下推才行。
sixth try
2020-06-13
终于成功压缩，并且理解了如何压缩成一维数组。start point需要注意。
### sixth try
class Solution(object):
"""
status shift: 确保每种前状态只有0--k个当前硬币，并且不重复，这样方才能保证结果中不出现重复
dp(i, v) = dp(i-1, v - 0*c) + dp(i-1, v - 1*c) + ... + dp(i-1, v-k * c)
start position:
dp(0, v) = 1, for any v
dp(i, 0) = 1, for any i, 这样可以使得dp(i-1, v - k*c) 在 v == kc的时候，至少是1.
next shift: 对状态转移方程进行压缩
dp(i, v-c) = dp(i-1, v - c) + dp(i-1, v - 2c) + ... dp(i-1, v-k*c)
dp(i, v) = dp(i-1, v) + dp(i, v-c)
next shift: 继续对转移方程进行压缩
观察：
dp(i, v) = dp(i-1, v) + dp(i, v-c)
可以对i进行压缩，使用一阶数组, dp[v]
- 对于dp(i-1, v), 每一轮i开始之前保存的都是i-1，走到v位置时候dp[v]获取的就是dp(i-1, v)
- 而对于dp(i, v-c), 每一轮走到v位置的时候， v-c位置上保存的已经是第i轮的数值，dp[v-c]也即dp(i, v-c)
start point:
dp[0]的时候，可以设置为1, 这样第一轮下来每一个都是1
"""
def waysToChange(self, n):
"""
:type n: int
:rtype: int
"""
mod = 1000000007
coins = [1, 5, 10, 25]
dp = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(len(coins)):
for j in range(n + 1):
if j >= coins[i]:
dp[j] = (dp[j] + dp[j-coins[i]]) % mod
return dp[n]
- 执行用时 :980 ms, 在所有 Python 提交中击败了17.26%的用户
- 内存消耗 :77.2 MB, 在所有 Python 提交中击败了100.00%的用户
Fifth Try
2020-06-13
第一次通过，学会通过公式推导得到简化版本，但问题在于看题解许多人是直接就到这个简化版本的，甚至是一维版本，目前我还是得一步一步按照思路推导才行。
### fifth try, 终于不超时了, f**k
### 时间1.3ms, 击败8.63用户; 空间142MB,击败100%用户？？？
class Solution(object):
"""
status shift: 确保每种前状态只有0--k个当前硬币，并且不重复，这样方才能保证结果中不出现重复
dp(i, v) = dp(i-1, v - 0*c) + dp(i-1, v - 1*c) + ... + dp(i-1, v-k * c)
start position:
dp(0, v) = 1, for any v
dp(i, 0) = 1, for any i, 这样可以使得dp(i-1, v - k*c) 在 v == kc的时候，至少是1.
next shift: 对状态转移方程进行压缩
dp(i, v-c) = dp(i-1, v - c) + dp(i-1, v - 2c) + ... dp(i-1, v-k*c)
dp(i, v) = dp(i-1, v) + dp(i, v-c)
"""
def waysToChange(self, n):
"""
:type n: int
:rtype: int
"""
coins = [1, 5, 10, 25]
cache = [[0 for i in range(n + 1)] for _ in range(len(coins))]
mod = 1000000007
for i in range(len(coins)):
for j in range(0, n+1):
if j == 0:
cache[i][j] = 1 # cache[i][0] == 1, start point
continue
if coins[i] <= j:
cache[i][j] = cache[i-1][j] + cache[i][j - coins[i]]
else:
cache[i][j] = cache[i-1][j]
return cache[len(coins)-1][n] % mod
- 执行用时 :1320 ms, 在所有 Python 提交中击败了8.63%的用户
- 内存消耗 :142.4 MB, 在所有 Python 提交中击败了100.00%的用户
Fourth Try （time exceeded version)
2020-06-13
最原始的动态规划版本，按照教材第一步走的路线，二维数组，遍历所有可能，但是超时了。测试了100以内的几个数字都没问题，提交后在900750的时候超时。
class Solution(object):
"""
status shift: 确保每种前状态只有0--k个当前硬币，并且不重复，这样方才能保证结果中不出现重复
dp(i, v) = dp(i-1, v - 0*c) + dp(i-1, v - 1*c) + ... + dp(i-1, v-k * c)
start position:
dp(0, v) = 1, for any v
dp(i, 0) = 1, for any i, 这样可以使得dp(i-1, v - k*c) 在 v == kc的时候，至少是1.
"""
def waysToChange(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 0:
return 0
coins = [1, 5, 10, 25]
cache = [[0 for i in range(n+1)] for c in range(len(coins))] # cache[c][n]
# cache[i][n] = cache[i-1][n] + cache[i-1][n-c] + ... + cache[i-1][n-kc], k = n // c
# 注意还包含了cache[i-1][n],也就是完全不使用coin[i]的情况
for i in range(len(coins)):
for num in range(0, n + 1):
if num == 0:
cache[i][num] = 1 # cache[i][0]都设置为1
continue
for k in range( num // coins[i] + 1):
if i == 0:
cache[i][num] = 1
else:
cache[i][num] += cache[i-1][num - k * coins[i]]
return cache[len(coins)-1][n]
参考别人
2020-06-12
https://leetcode-cn.com/problems/coin-lcci/comments/363262
问题是我一直觉得这种方法有漏洞，dp[i][j] = dp[i-1][j] + dp[i][j-rule[i], 怎么dp[i]j-rule[i]]就不会包含dp[i-1][j]中的子集呢？？凭什么dp[i]j-rule[i]]就一定使用i呢？ dp[i][j]代表使用前i种硬币，但是也包含了dp[i-1]啊？！！！！ f**k.
这么几天，一直无法理解的是所谓的前i种物品的说法，前i种物品怎么就能凑成所有组合了？？？ 前4种物品，那么什么时候能覆盖第1种和第5种之间的混合？ 还有什么打表法？？？
note:后来的理解，从第一个推导公式往下压缩，就能理解了。
class Solution {
public int waysToChange(int n) {
int mod = 1000000007;
int rule[] = {1,5,10,25};
int dp[][] = new int [4][n+1];
for(int i=0;i<4;i++)
{
dp[i][0] = 1;
for(int j=1;j<=n;j++)
{
if(i>0)
dp[i][j] = dp[i-1][j];
if(j>=rule[i])
dp[i][j] = (dp[i][j]+dp[i][j-rule[i]])%mod;
}
}
return dp[3][n];
}
}
Second Try (time exceeded version)
2020-06-12
统计每个硬币只用1到maxn次的次数，新一轮的调用就不再使用该硬币种类了，避免了first try中1-5和5-1被统计为两次的问题，纯粹是递归调用暴力遍历。
算1000的时候就超时了，100还是正确的，因为完全没有使用到cache缓存，也就没有使用动态规划。代码里用了dp名字，本来是想写成动态规划的，，是因为每个n都对应了n和coins列表，也不知道怎么缓存应用了。不过复杂度得上指数级别了。
class Solution(object):
def waysToChange(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 0:
return 0
coins = [1, 5, 10, 25]
cache = ["" for i in range(n+1)]
def dp(n, coins):
if n == 0:
return 1
if len(coins) == 0:
return 0
selected = coins.pop()
maxn = n // selected
rv = 0
for i in range(0, maxn + 1):
rv += dp(n - i * selected, coins + [])
# print(n, selected, coins, rv)
return rv % 1000000007
rv = dp(n, coins)
return rv
测试用例，可以用来理解
输入
10
输出
4
预期结果
4
stdout
(10, 1, [], 1)
(5, 1, [], 1)
(10, 5, [1], 3)
(10, 10, [1, 5], 4)
(10, 25, [1, 5, 10], 4)
First Try (bug version)
2020-06-12
写出了错误版本，被这道题虐惨了，总是理解不了。
这种写法会导致1-5和5-1被统计为两种可能。
class Solution(object):
def waysToChange(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 0:
return 0
coins = [1, 5, 10, 25]
cache = ["" for i in range(n+1)]
def dp(n):
if n <= 4:
return 1
if cache[n] != "":
return cache[n]
rv = 0
for c in coins:
if n - c < 0:
continue
rv += dp(n-c)
cache[n] = rv
return rv
dp(n)
return cache[n]