换零钱

[编程题]换零钱

热度指数：6039 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有一个数组changes，changes中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，对于一个给定值x，请设计一个高效算法，计算组成这个值的方案数。

给定一个int数组changes，代表所有零钱，同时给定它的大小n，另外给定一个正整数x，请返回组成x的方案数，保证n小于等于100且x小于等于10000。

测试样例：

[5,10,25,1],4,15

返回：6

测试样例：

[5,10,25,1],4,0

返回：1

算法知识视频讲解

Python

lx的流星

# -*- coding:utf-8 -*-

class Exchange:
    def countWays(self,changes,n,x):
        # write code here
        dp=[]
        for i in range(n):
            dp.append([0]*(x+1))
        for i in range(n):
            dp[i][0]=1

        j=0
        while j*changes[0]<=x:
            dp[0][j*changes[0]]=1
            j+=1
        for i in range(1,n):
            for j in range(1,x+1):
                if j-changes[i]>=0:
                    dp[i][j]=dp[i-1][j]+dp[i][j-changes[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[-1][-1]

发表于 2019-07-20 14:41:03 回复(0)