换零钱--动态规划

矫情吗；* 2022-08-18 01:59 129阅读 0赞

题目示例：

【题目】

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

【举例】

arr=\[5,10,25,1\]，aim=0。

组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。

arr=\[5,10,25,1\]，aim=15。

组成15元的方法有6种，分别为3张5元，1张10元+1张5元，1张10元+5张1元，10张1元+1张5元，2张5元+5张1元，15张1元。所以返回6。

arr=\[3,5\]，aim=2。

任何方法都无法组成2元。所以返回0。

解法一：暴力递归求解

/* 递归求解 */
    int process1(vector<int> arr, int index, int aim)
    {
        int res = 0;
        int i = 0;
    
        if (index == arr.size())
        {
            res = (aim == 0 ? 1:0);
        }
        else
        {
            for(i = 0; aim >= (arr[index]*i); i++)
            {
                res += process1(arr,index+1, aim - arr[index]*i);
            }
        }
    
        return res;
    }
    
    /* 暴力递归求解 */
    int getCoinSorts1(vector<int> arr, int aim)
    {
        if (arr.empty() || aim < 0)
        {
            return 0;
        }
    
        /* 求0到aim所有可能 */
        return process1(arr,0, aim);
    }

解法二：动态规划 dp\[i\]\[j\] = dp\[i\]\[j-arr\[i\]\] + dp\[i-1\]\[j\]

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    #define CHANGE_NUMBERS 4
    #define MAX_AIM 1000
    
    
    /* 暴力递归求解 */
    int getCoinSorts2(vector<int> arr,const int aim)
    {
        if (arr.empty() || aim < 0)
        {
            return 0;
        }
    
        int i = 0, j = 0;
        int result = 0;
    
        int dp[CHANGE_NUMBERS][MAX_AIM] = {0};
        /* 先求第一列的值 */
        for(i = 0; i < arr.size(); i++)
        {
            dp[i][0] = 1;
        }
    
        /* 再求第一行的值 */
        for(j = 1; arr[0]*j <= aim; j++)
        {
            dp[0][arr[0]*j] = 1;
        }
    
        /* 再求其他行和列的值 */
        for(i = 1; i < arr.size(); i++)
        {
            for(j = 1; j <= aim; j++)
            {
                dp[i][j] = dp[i-1][j];
                dp[i][j] += ((j - arr[i]) >= 0) ? dp[i][j-arr[i]] : 0;
            }
        }
    
        return dp[arr.size()-1][aim];
    }
    
    int main( void )
    {
        int a[4] = {5,10,25,1};
        vector<int> arr(a,a+4) ;
    
        cout << getCoinSorts2(arr,15) << endl;
    
    
        return 0;
    }