有数组penny,penny中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim(小于等于1000)代表要找的钱数,求换钱有多少种方法。

  给定数组 penny 及它的大小(小于等于50),同时给定一个整数aim,请返回有多少种方法可以凑成aim。

  测试样例:

[1,2,4],3,3

  返回:

2

-w814

Solutions

  这个题目说是能够吧暴力搜索、记忆化搜索和动态规划串联起来了。

暴力搜索法

  要搞清楚暴力搜索过程。

# -*- coding:utf-8 -*-
class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        if penny is None or aim == 0:
            return 0
        return self.foo(penny, 0, aim)
    
    def foo(self, arr, index, aim):
        res = 0
        if index == len(arr):
            res = 1 if aim == 0 else 0
        else:
            for i in range(aim + 1):
                if arr[index] * i > aim:
                    break
                res += self.foo(arr, index + 1, aim - arr[index] * i)
        return res

记忆化搜索法

  我们可以看到在递归过程中,很有可能会出现重复计算的问题,那么我们通过空间换时间的办法,把递归时计算过的结果保存下来。

# 记忆化搜索法
import java.util.*;

public class Exchange {
    public int countWays(int[] penny, int n, int aim) {
        // write code here
        if (penny == null || penny.length == 0 || aim <= 0) 
            return 0;
        int [][] map = new int[penny.length+1][aim+1];
        return process2(penny, 0, aim, map);
    }
    public int process2(int[] arr, int index, int aim, int[][] map)
    {
        int res = 0;
        if(index == arr.length){
            res = aim == 0? 1: 0;
        }else{
            int mapValue = 0;
            for (int i = 0; arr[index] * i <= aim; i++){
                mapValue = map[index+1][aim-arr[index]*i];
                if(mapValue!=0){
                    res += mapValue == -1?0:mapValue;
                }else{
                    res += process2(arr, index+1, aim-arr[index]*i, map);
                }   
            }
        }
        map[index][aim] = res == 0? -1:res;
        return res;
    }
}

  我对照着用 Python 实现了一遍,就是有问题我勒个去啊!?

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

class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        if penny is None or len(penny) == 0 or aim < 0:
            return 0
        row, col = len(penny) + 1, aim + 1
        # dp = [[0] * col] * row
        mp = [[0] * col for _ in range(row)]
        return self.foo(penny, 0, aim, mp)
    
    def foo(self, arr, index, aim, mp):
        res = 0
        if index == len(arr):
            res = 1 if aim == 0 else 0
        else:
            for i in range(aim + 1):
                if arr[index] * i > aim:
                    break
                mp_val = mp[index + 1][aim - arr[index] * i]
                if mp_val != 0:
                    res += 0 if mp_val == -1 else mp_val
                else:
                    res += self.foo(arr, index + 1, aim - arr[index] * i, mp)
        
        if res == 0:
            mp[index][aim] = -1
        else:
            mp[index][aim] = res
        return res

动态规划

  记忆化过程其不规定计算顺序(不管状态路径),而动态规划严格规定计算顺序。先使用比较复杂的二维状态转移公式: -w1543

  计算 dp[i][j] 时,需要所有取当前 i 面值货币张数的的所有情况累加。

import java.util.*;

public class Exchange {
    public int countWays(int[] penny, int n, int aim) {
        // write code here
        if (penny == null || penny.length == 0 || aim <= 0) 
            return 0;
        int [][] dp = new int[penny.length][aim+1];
        for (int i = 0; i < penny.length; i++){
            dp[i][0] = 1;
        }
        for (int j = 1; penny[0] * j <= aim; j++){
            dp[0][penny[0] * j] = 1;
        }
        int num = 0;
        for (int i = 1; i < penny.length; i++){
            for (int j = 1; j <= aim; j++){
                num = 0;
                for (int k = 0; j - penny[i] * k >= 0; k++){
                    num += dp[i-1][j - penny[i] * k];
                }
                dp[i][j] = num;
            }
        }
        return dp[penny.length-1][aim];
    }
}

  还是那样,用 Python 实现一遍就是错错错!!!找到错误的原因了……尼玛,原来是浅拷贝的原因。代码中注释的部分体现了动态规划的状态转移矩阵,自我体会一下这里表示的意思。

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

class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        if penny is None or len(penny) == 0 or aim < 0:
            return 0
        row, col = len(penny), aim + 1
        # dp = [[0] * col] * row
        dp = [[0 for _ in range(col)] for _ in range(row)]
        for i in range(len(penny)):
            dp[i][0] = 1
        for j in range(1, aim + 1):
            if penny[0] * j > aim:
                break
            dp[0][penny[0] * j] = 1
        for i in range(1, len(penny)):
            for j in range(1, aim + 1):
                # if j >= penny[i]:
                #     dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]]
                # else:
                #     dp[i][j] = dp[i - 1][j]

                num = 0
                k = 0
                while j - penny[i] * k >= 0:
                    num += dp[i - 1][j - penny[i] * k]
                    k += 1
                dp[i][j] = num
        return dp[len(penny) - 1][aim]

  然后是使用空间压缩,进一步优化得到更低的时间复杂度:

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

class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        if penny is None or len(penny) == 0 or aim < 0:
            return 0
        # dp = [[0] * col] * row
        dp = [0] * (aim + 1)
        for j in range(0, aim + 1):
            if penny[0] * j > aim:
                break
            dp[penny[0] * j] = 1
        for i in range(1, len(penny)):
            for j in range(1, aim + 1):
                if j >= penny[i]:
                    dp[j] += dp[j - penny[i]]
        return dp[aim]

References

  1. 第2节 找零钱练习题
  2. 拓展