J*****4
发帖数: 1 | 1 https://en.wikipedia.org/wiki/Change-making_problem
leetcode 322题
我的算法python源码
‘’‘
import math
import time
'''old way dp to amount'''
class Solution_old:
def coinChange(self, coins, amount: int) -> int:
dp = [math.inf] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
if dp[amount] == math.inf:
return -1
else:
return dp[amount]
def get_gcd(a, b):
if a >= b:
n1 = a
n2 = b
else:
n1 = b
n2 = a
while True:
m = n1 % n2
if m == 0:
return n2
else:
n1 = n2
n2 = m
'''new way , do not always dp to amount'''
class Solution_new:
def coinChange(self, coins, amount: int) -> int:
if amount == 0:
return 0
if len(coins) == 0 :
return -1
if len(coins)==1:
if amount % coins[0] !=0:
return -1
else:
return amount//coins[0]
gcd = coins[0]
for i in range(1,len(coins)):
gcd = get_gcd(gcd, coins[i])
if (amount % gcd) != 0:
return -1
else:
amount=amount // gcd
imax=coins[0]//gcd
imin=imax
for i in range(len(coins)):
coins[i]=coins[i]//gcd
if coins[i]>imax:
imax=coins[i]
if coins[i]
imin=coins[i]
if amount < imin:
return -1
cnt = 0
i = imin
table = [math.inf]*imin
table[0]=0
while cnt < imax:
min_n =math.inf
for c in coins:
if c <= i:
min_n = min(min_n, table[i - c] + 1)
table.append(min_n)
if i>=imax:
min_pre=table[i - imax]
else:
min_pre=math.inf
if min_n - min_pre != 1:
cnt = 0
else:
cnt += 1
if amount == i:
if min_n == math.inf:
return -1
else:
return min_n
i += 1
start = i - imax-1
m = amount // imax
v_mod = amount % imax
i = start // imax
i_mod = start % imax
if v_mod < i_mod:
i = i + 1
index = v_mod + i * imax
ret = (m - i + table[index])
if ret == math.inf:
return -1
else:
return ret
if __name__=="__main__":
#run time compare
s = Solution_old()
coins = [186, 419, 83, 408]
a = time.time()
print(s.coinChange(coins, 1000000))
print(time.time() - a)
s=Solution_new()
coins=[186,419,83,408]
a=time.time()
print(s.coinChange(coins, 1000000))
print(time.time()-a)
""" result on my computer
2388
1.5335829257965088
2388
0.0724637508392334
"""
’‘’ | J*****4
发帖数: 1 | 2 就是给定一组面值不一样的硬币，再给定一个目标数字N，求组成这个数字的最少的硬
币数量。我目前看到的最优时间复杂度都是随N线性增长的。我这个算法时间复杂度并
不随N线性增加，更加优化。各位怎么看？ | J*****4
发帖数: 1 | 3 奇怪，怎么没人给点想法或意见。究竟算不算一个更好的算法？ | J*****4
发帖数: 1 | 4 我的这个算法时间复杂度不会超过最大的两个coin值的乘积。
比如coins=[1,2,5] 则时间复杂度不会超过10， 无论amount是多少
比如coins=[1,2,5,9] 则时间复杂度不会超过45， 无论amount是多少
直觉如此，未严格证明，大家看我这个算法对吗？ | E**********e
发帖数: 1736 | 5 先顶在下载。
【在 J*****4 的大作中提到】
: 我的这个算法时间复杂度不会超过最大的两个coin值的乘积。
: 比如coins=[1,2,5] 则时间复杂度不会超过10， 无论amount是多少
: 比如coins=[1,2,5,9] 则时间复杂度不会超过45， 无论amount是多少
: 直觉如此，未严格证明，大家看我这个算法对吗？
| J*****4
发帖数: 1 | 6 终于有人感兴趣研究下了，感谢感谢
: 先顶在下载。
【在 E**********e 的大作中提到】
: 先顶在下载。
| J*****4
发帖数: 1 | 7 https://en.wikipedia.org/wiki/Change-making_problem
leetcode 322题
我的算法python源码
‘’‘
import math
import time
'''old way dp to amount'''
class Solution_old:
def coinChange(self, coins, amount: int) -> int:
dp = [math.inf] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
if dp[amount] == math.inf:
return -1
else:
return dp[amount]
def get_gcd(a, b):
if a >= b:
n1 = a
n2 = b
else:
n1 = b
n2 = a
while True:
m = n1 % n2
if m == 0:
return n2
else:
n1 = n2
n2 = m
'''new way , do not always dp to amount'''
class Solution_new:
def coinChange(self, coins, amount: int) -> int:
if amount == 0:
return 0
if len(coins) == 0 :
return -1
if len(coins)==1:
if amount % coins[0] !=0:
return -1
else:
return amount//coins[0]
gcd = coins[0]
for i in range(1,len(coins)):
gcd = get_gcd(gcd, coins[i])
if (amount % gcd) != 0:
return -1
else:
amount=amount // gcd
imax=coins[0]//gcd
imin=imax
for i in range(len(coins)):
coins[i]=coins[i]//gcd
if coins[i]>imax:
imax=coins[i]
if coins[i]
imin=coins[i]
if amount < imin:
return -1
cnt = 0
i = imin
table = [math.inf]*imin
table[0]=0
while cnt < imax:
min_n =math.inf
for c in coins:
if c <= i:
min_n = min(min_n, table[i - c] + 1)
table.append(min_n)
if i>=imax:
min_pre=table[i - imax]
else:
min_pre=math.inf
if min_n - min_pre != 1:
cnt = 0
else:
cnt += 1
if amount == i:
if min_n == math.inf:
return -1
else:
return min_n
i += 1
start = i - imax-1
m = amount // imax
v_mod = amount % imax
i = start // imax
i_mod = start % imax
if v_mod < i_mod:
i = i + 1
index = v_mod + i * imax
ret = (m - i + table[index])
if ret == math.inf:
return -1
else:
return ret
if __name__=="__main__":
#run time compare
s = Solution_old()
coins = [186, 419, 83, 408]
a = time.time()
print(s.coinChange(coins, 1000000))
print(time.time() - a)
s=Solution_new()
coins=[186,419,83,408]
a=time.time()
print(s.coinChange(coins, 1000000))
print(time.time()-a)
""" result on my computer
2388
1.5335829257965088
2388
0.0724637508392334
"""
’‘’ | J*****4
发帖数: 1 | 8 就是给定一组面值不一样的硬币，再给定一个目标数字N，求组成这个数字的最少的硬
币数量。我目前看到的最优时间复杂度都是随N线性增长的。我这个算法时间复杂度并
不随N线性增加，更加优化。各位怎么看？ | J*****4
发帖数: 1 | 9 奇怪，怎么没人给点想法或意见。究竟算不算一个更好的算法？ | J*****4
发帖数: 1 | 10 我的这个算法时间复杂度不会超过最大的两个coin值的乘积。
比如coins=[1,2,5] 则时间复杂度不会超过10， 无论amount是多少
比如coins=[1,2,5,9] 则时间复杂度不会超过45， 无论amount是多少
直觉如此，未严格证明，大家看我这个算法对吗？ | E**********e
发帖数: 1736 | 11 先顶在下载。
【在 J*****4 的大作中提到】
: 我的这个算法时间复杂度不会超过最大的两个coin值的乘积。
: 比如coins=[1,2,5] 则时间复杂度不会超过10， 无论amount是多少
: 比如coins=[1,2,5,9] 则时间复杂度不会超过45， 无论amount是多少
: 直觉如此，未严格证明，大家看我这个算法对吗？
| J*****4
发帖数: 1 | 12 终于有人感兴趣研究下了，感谢感谢
: 先顶在下载。
【在 E**********e 的大作中提到】
: 先顶在下载。
| J*****4
发帖数: 1 | 13 再说详细点：
问题描述：
给你几个不同面值的硬币coins和一个总钱数 amount，求组成amount的最少硬币数量，
如果没有解，则返回-1
Examples:
Input : coins = [1, 2, 5], amount = 11
最少组成是两个5和一个1，所以
Output :3
Input :coins = [ 2, 5], amount = 8
无解
Output : -1
1:传统解法
假设 F(n) 是对于amount = n 的答案, 硬币数量是s.
则F(n) = min( F(n -coin[0])+1,F(n -coin[1])+1,...,F(n-coin[s-1])+1)
我们 从 F(0)开始用动态规划算法得到 F(n).
[sourcecode language="Python3" highlight=""]
def coinChange(coins: List[int], amount: int) -> int:
dp=[math.inf]*(amount+1)
dp[0] = 0
for i in range(1,amount+1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
if dp[amount]==math.inf:
return -1
else:
return dp[amount]
[/sourcecode]
时间复杂度 : O(s*n) s是硬币数量， n是amount的值
2: 因为如下的两个输入的答案是一样的 :coins = [ 2, 5], amount = 101 和输入 :
coins = [ 4, 10], amount = 202. 所以先用最大公约数gcd可以减少时间复杂度到 O(
s*n/gcd) .
[sourcecode language="Python3" highlight=""]
import math
def get_gcd(a, b):
if a >= b:
n1 = a
n2 = b
else:
n1 = b
n2 = a
while True:
m = n1 % n2
if m == 0:
return n2
else:
n1 = n2
n2 = m
def coinChange(coins, n):
# some corn cases
if n == 0:
return 0
if len(coins) == 0:
return -1
if len(coins) == 1:
if n % coins[0] != 0:
return -1
else:
return n // coins[0]
gcd = coins[0]
for i in range(1, len(coins)):
gcd = get_gcd(gcd, coins[i])
if (n % gcd) != 0:
return -1
else:
n = n // gcd
imax = coins[0] // gcd
imin = imax
for i in range(len(coins)):
coins[i] = coins[i] // gcd
if coins[i] > imax:
imax = coins[i]
if coins[i] < imin:
imin = coins[i]
if n < imin:
return -1
mins = [math.inf] * (n + 1)
mins[0] = 0
for i in range(1,n+1):
for c in coins:
if c <= i:
mins[i]=min(mins[i],mins[i-c]+1)
if mins[-1] == math.inf:
return -1
else:
return mins[-1]
[/sourcecode]
3: 新算法. 如果coins 的 gcd =1(if gcd 不等于1,我们可以简化为1) , 假设amount=
n 的答案 F(n). 必然存在一个数字m , 对于每一个大于m的数i, F(i)=F(i-maxcoin)
+1. 所以如果 n > m , 我们可以通过计算得到 F(n) .
时间复杂度 : min(O(s*n), O(s*m)) ,m 数值应该是两个最大的币值乘值同一个级别。
Examples:
Input :coins = [ 2, 5]
F(0) : 0
....
....
F(8) : -1
F(9) : 3
F(10) : 2
F(11) : 4
F(12) : 3
F(13) : 5
F(14) : 4 = F(14-5) +1 //从n=14后就满足F(i)=F(i-maxcoin) +1
F(15) : 3 = F(15-5) +1
...
对于输入 coins =[2,5] ,n . 因为 m = 14. 所以不管 n 是多大，时间复杂度不会超
过 s*m = 2 *(14+5) =38.
[sourcecode language="Python3" highlight=""]
import math
def get_gcd(a, b):
if a >= b:
n1 = a
n2 = b
else:
n1 = b
n2 = a
while True:
m = n1 % n2
if m == 0:
return n2
else:
n1 = n2
n2 = m
def coinChange(coins, n):
if n == 0:
return 0
if len(coins) == 0:
return -1
if len(coins) == 1:
if n % coins[0] != 0:
return -1
else:
return n // coins[0]
gcd = coins[0]
for i in range(1, len(coins)):
gcd = get_gcd(gcd, coins[i])
if (n % gcd) != 0:
return -1
else:
n = n // gcd
imax = coins[0] // gcd
imin = imax
for i in range(len(coins)):
coins[i] = coins[i] // gcd
if coins[i] > imax:
imax = coins[i]
if coins[i] < imin:
imin = coins[i]
if n < imin:
return -1
cnt = 0
i = imin
table = [math.inf] * (n + 1)
table[0] = 0
while cnt < imax:
for c in coins:
if c <= i:
table[i] = min(table[i], table[i - c] + 1)
if i >= imax:
min_pre = table[i - imax]
else:
min_pre = math.inf
if table[i] - min_pre != 1:
cnt = 0
else:
cnt += 1
if n == i:
if table[i] == math.inf:
return -1
else:
return table[i]
i += 1
start = i - imax - 1
times = (n - start) // imax
index = (n - start) % imax + start
return (times + table[index])
[/sourcecode] |
|
