题解 | #牛牛的超市#

题目：
定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 元换成若干零钱，请问有多少种换钱的方案？
方法一：动态规划
这是背包问题的变形，我们可以定义dp[i][j]为用前i种硬币凑出金额j的方案数，
初始条件为 $dp[i][0]=1$ ,因为前i种硬币凑出金额0的方案数为1
第i种硬币数量有a[i-1][1]个，因此枚举第i种硬币的数量，则前i种硬币凑出金额j的方案数等于前 $i-1$ 种硬币凑出金额j不加入k个第i种硬币的方案数的累加和，因此状态转移方程为 $dp[i][j]+=dp[i-1][j-k*a[i-1][0]],j>=k*a[i-1][0]$

图片说明

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型二维数组 ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    public int solve (int n, int x, int[][] a) {
        // write code 
        //用前i种币值凑出金额j的方案数为dp[i][j]
        int[][]dp=new int[n+1][x+1];
        for(int i=0;i<=n;i++)dp[i][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=x;j++){
                for(int k=0;k<=a[i-1][1];k++){//枚举第i种硬币的个数
                    if(j>=k*a[i-1][0])//如果金额数量大于等于k个第i种硬币则可以将k个第i种硬币放入
                        dp[i][j]+=dp[i-1][j-k*a[i-1][0]];
                    else break;
                }
            }
        }
        return dp[n][x];
    }
}

复杂度：
时间复杂度： $图片说明$ ,三层循环，最内层循环k循环次数不超过 $max(a[i][1])$
空间复杂度： $O(nx)$ ,dp数组的大小不超过 $n*x$
方法二：记忆化搜索
将动态规划改写为记忆化搜索，用记忆数组记录已经计算过的方案数，避免大量的重复运算
递归公式为：

$i>=0并且j==0,f=1;$
$i==0并且j>0,f=0;$
$memory[i][j]+=f(i-1,j-k*a[i-1][0],a)$
图片说明

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型二维数组 ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    int[][]memory;
    public int solve (int n, int x, int[][] a) {
        // write code 
        //用i种币值凑出金额j的方案数为dp[i][j]
        memory=new int[n+1][x+1];
        for(int i=0;i<a.length;i++)memory[i][0]=1;//初始化记忆数组，i种硬币凑出金额0的方案数都为1
        return dp(n,x,a);
    }
    int dp(int i,int j,int[][]a){
        //递归终止条件
        if(i>=0&&j==0)return 1;
        if(i==0&&j>0)return 0;
        //已经计算过值直接返回    
        if(memory[i][j]!=0)return memory[i][j];
        //前i种硬币凑成金额j的方案数由前i-1种硬币凑出金额j-k个第i种硬币的方案数递推而来
        for(int k=0;k<=a[i-1][1];k++){
            if(j>=k*a[i-1][0])
                memory[i][j]+=dp(i-1,j-k*a[i-1][0],a);
        }
        return memory[i][j];
    }
}

复杂度：
时间复杂度：递归次数不超过 $n*x$ ，每次递归时间复杂度为 $O(max(a[i][1]))$ ,因此时间复杂度为 $图片说明$
空间复杂度： $O(x*n)$ ,记忆数组和递归运行时栈大小不超过 $n*x$