算法之Python实现 - 003 ：换钱的方法数 - Python

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题目】给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求组成aim的方法数。

【代码1】递归

import numpy as np

def changemeans(arr,aim):

    if len(arr)<0:

        print("No coin provided for change!")

    arr.sort()

    arr.reverse()

    m = process(arr,0,aim)

    print('There are ',m,' ways!')

def process(arr,idx,aim):

    res = 0

    i = 0

    if aim == 0:

        res = 1

    else :

        if idx == len(arr):

            res = 0

        else :

            while arr[idx]*i <= aim:

                res += process(arr,idx+1,aim - arr[idx]*i)

                i += 1

    return res

# ===CALL === #

a = [5,10,25,1]

tar = 1000

changemeans(a,tar)

【代码2】改进递归（递归加入记忆搜索）：时间复杂度O(N * aim ² )

【原理】：例如按照题目中的a = [5,10,25,1]，使用a[0]和a[1]，利用[25,1]组成剩余的980元的可能性就是一种重复递归，假设利用[25,1]组成剩余的980元需要5秒钟，那么【代码1】需要搜索5*0+10*2,5*2+10*1,5*5 三次递归，【代码2】额外耗用了O((N+1)*(aim+1))的空间，但是只要三次寻址即可。

import numpy as np

def changemeans(arr,aim):

    if len(arr)<0:

        print("No coin provided for change!")

    arr.sort()

    arr.reverse()

    map = np.zeros((len(arr)+1,aim+1))

    m = process(arr,0,aim,map)

    print('There are ',m,' ways!')

def process(arr,idx,aim,map):

    res = 0

    i = 0

    if aim == 0:

        res = 1

    else :

        if idx == len(arr):

            res = 0

        else :

            while arr[idx]*i <= aim:

                mapval = map[idx+1][aim- arr[idx]*i]

                if mapval != 0:

                    if mapval == -1:    mapval = 0

                    res += mapval

                else:

                    res += process(arr,idx+1,aim - arr[idx]*i,map)

                i += 1

    if res == 0:

        map[idx][aim] = -1

    else :

        map[idx][aim] = res

    #print(':',int(map[idx][aim]),res)

    return res

# ===CALL === #

a = [5,10,25,1]

tar = 1000

changemeans(a,tar)

【代码3】：时间复杂度O(N * aim ² )

import numpy as np

def changemeans(arr,aim):

    n = len(arr)

    if n<=0:

        print('No coin provided for exchange.')

    j = 0

    dp = np.zeros((n,aim+1))

    for i in range(0,n):

        dp[i][0] = 1

    while j*arr[0]<= aim:

        dp[0][j*arr[0]] = 1

        j += 1

    for i in range(1,n):

        for j in range(1,aim+1):

            num  = 0

            k = 0

            while j-arr[i]*k >= 0:

                num += dp[i-1][j-arr[i]*k]

                k += 1

            dp[i][j] = num

    print(dp[n-1][aim])

# ===CALL === #

a = [5,10,25,1]

tar = 1000

changemeans(a,tar)

【代码4】：

另外实际上算arr[0..i-1]的组成剩下的方法，只会从最少的那个钱币为下标的位置开始，因此可以改为：

import numpy as np

def changemeans(arr,aim):

    n = len(arr)

    if n<=0:

        print('No coin provided for exchange.')

    j = 0

    dp = np.zeros((n,aim+1))

    for i in range(0,n):

        dp[i][0] = 1

    while j*arr[0]<= aim:

        dp[0][j*arr[0]] = 1

        j += 1

    for i in range(1,n):

        for j in range(min(arr)-1,aim+1):

            num  = 0

            k = 0

            while j-arr[i]*k >= 0:

                num += dp[i-1][j-arr[i]*k]

                k += 1

            dp[i][j] = num

    print(dp[n-1][aim])

# ===CALL === #

a = [5,10,25,2]

tar = 1000

changemeans(a,tar)