返回信息流In England the currency is made up of pound, ?, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, ?1 (100p) and ?2 (200p).
It is possible to make ?2 in the following way:
1×?1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can ?2 be made using any number of coins?
链接：https://projecteuler.net/problem=31
解法中
#include <stdio.h>
int countWays(int total,int set[],int size){
if (total<0)
return 0;
if (total==0)//////////////////////这里有点不懂，求解答
return 1;
if (size==1)//////////这里也是不懂，求解答
return 1;
else
return countWays(total,set,size-1)+countWays(total-set[size-1],set,size);
}
int main(){
int total=200;
int set[]={1,2,5,10,20,50,100,200};
int result;
int size = 8;
result = countWays(total,set,size);
printf("%d\n",result);
return 0;
}
动态规划的基本原理了解，但是那两个初始条件不太懂
这是一条镜像帖。来源：北邮人论坛 / cpp / #89327同步于 2015/11/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
EulerProject 31题 动态规划 求指导
UC1451427216
2015/11/1镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
total == 0：要凑 0 块钱，方法数为 1
size == 1：只用面值为 1 块的钱去凑某个数量，方法数为 1
乱来个非递归版
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def make_coin(coins, n):
ways = [[0 for col in range(n + 1)] for row in range(len(coins))]
for i in range(n + 1):
ways[0][i] = 1
for i in range(len(coins)):
for value in range(n + 1):
k = value
while k >= 0:
ways[i][value] += ways[i - 1][k]
k -= coins[i]
return ways[len(coins) - 1][n]
if __name__ == '__main__':
print(make_coin([1, 2, 5, 10, 20, 50, 100, 200], 200))
1. 用当前的硬币构造0的面值，有1种方案；
2. 如果当前只剩下最后一种硬币（面值为1），那么只有1种方案。这一句也可以改成：if (size == 0) return 0。
另外这个动态规划的实现有问题，它的复杂度不是线性的，因为没有记忆化，同一个状态会被重复计算。
【 在 UC1451427216 的大作中提到: 】
: In England the currency is made up of pound, ?, and pence, p, and there are eight coins in general circulation:
: 1p, 2p, 5p, 10p, 20p, 50p, ?1 (100p) and ?2 (200p).
: It is possible to make ?2 in the following way:
: ...................
谢谢指导哈，可是算出来的答案是正确的。
【 在 wooden 的大作中提到: 】
: 1. 用当前的硬币构造0的面值，有1种方案；
: 2. 如果当前只剩下最后一种硬币（面值为1），那么只有1种方案。这一句也可以改成：if (size == 0) return 0。
: 另外这个动态规划的实现有问题，它的复杂度不是线性的，因为没有记忆化，同一个状态会被重复计算。
: ...................
是啊，正确性没什么问题，但是这个复杂度是指数级的，数据规模大一些这代码就挂了。
【 在 UC1451427216 的大作中提到: 】
: 谢谢指导哈，可是算出来的答案是正确的。