BM70兑换零钱

​

描述

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

如果无解，请返回-1.

$0<=n<=10000$,$0<=val <= 10000$

$0<=aim<=10000$

解题代码

钱币遍历体积

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    /**
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int t) {
        // write code here
        //cost is 1
        int n = arr.size();
        if(n<=0) return -1;
        int max = t+1;
        vector<int> dp(t+1,max);

        dp[0] = 0;
        
        for(int i=0;i<n;i++) {
            for(int j=arr[i];j<=t;j++) {
                  dp[j] = min(dp[j],dp[j-arr[i]] + 1);
            }
        }
        
        return dp[t] == max?-1:dp[t];
    }
};

从体积去遍历 钱币

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    /**
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int t) {
        // write code here
        //cost is 1
        int n = arr.size();
        if(n<=0) return -1;
        int max = t+1;
        vector<int> dp(t+1,max);
//         dp[t]  = INT_MAX;
        dp[0] = 0;
        
        for(int i=1;i<=t;i++) {
            for(int j=0;j<n;j++) {
                if(i<arr[j]) continue;
                //i>=arr[j]
                dp[i] = min(dp[i],dp[i-arr[j]]+1);
            }
        }
        
        return dp[t] == max?-1:dp[t];
    }
};