解题思路

  1. 问题分析：

    • 每种面值的货币可以使用任意张（完全背包特征）
    • 目标是找到组成 的最少货币数
    • 无法组成时返回 -1

  2. 动态规划设计：

    • 状态定义： 表示组成金额 所需的最少货币数
    • 初始化：，其他为无穷大
    • 状态转移：
    • 其中 是当前面值

  3. 优化：

    • 使用一维 数组（滚动数组）
    • 正序遍历（完全背包特征）

代码

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minCoins(vector<int>& arr, int aim) {
    if(aim == 0) return 0;
    
    vector<int> dp(aim + 1, INT_MAX);
    dp[0] = 0;
    
    // 遍历每种面值
    for(int coin : arr) {
        // 完全背包正序遍历
        for(int j = coin; j <= aim; j++) {
            // 只有当dp[j-coin]不是无穷大时才更新
            if(dp[j-coin] != INT_MAX) {
                dp[j] = min(dp[j], dp[j-coin] + 1);
            }
        }
    }
    
    return dp[aim] == INT_MAX ? -1 : dp[aim];
}

int main() {
    int n, aim;
    cin >> n >> aim;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << minCoins(arr, aim) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int minCoins(int[] arr, int aim) {
        if(aim == 0) return 0;
        
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        // 遍历每种面值
        for(int coin : arr) {
            // 完全背包正序遍历
            for(int j = coin; j <= aim; j++) {
                // 只有当dp[j-coin]不是无穷大时才更新
                if(dp[j-coin] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j-coin] + 1);
                }
            }
        }
        
        return dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(minCoins(arr, aim));
        sc.close();
    }
}

def min_coins(arr: list, aim: int) -> int:
    if aim == 0:
        return 0
        
    dp = [float('inf')] * (aim + 1)
    dp[0] = 0
    
    # 遍历每种面值
    for coin in arr:
        # 完全背包正序遍历
        for j in range(coin, aim + 1):
            # 只有当dp[j-coin]不是无穷大时才更新
            if dp[j-coin] != float('inf'):
                dp[j] = min(dp[j], dp[j-coin] + 1)
    
    return dp[aim] if dp[aim] != float('inf') else -1

if __name__ == "__main__":
    n, aim = map(int, input().split())
    arr = list(map(int, input().split()))
    print(min_coins(arr, aim))

算法及复杂度

  • 算法：动态规划（完全背包）
  • 时间复杂度：， 是货币种类数， 是目标金额
  • 空间复杂度：，使用一维 数组