一、思路讲解

1. 当前操作

遍历到第i种货币时，针对每个金额j，计算使用前i种货币组成金额j的最少货币数，核心是判断是否选择当前货币，并更新最优解。

2. 子问题

已知使用前i-1种货币组成任意金额的最少货币数（即dp[i-1][...]），推导使用前i种货币组成金额j的最少货币数（即dp[i][j]）；最终通过dp[n][aim]得到使用所有货币组成aim的最少货币数。

3. 下一个子问题

• 若不选第i种货币：则dp[i][j]直接继承前i-1种货币组成j的结果（dp[i-1][j]）；
• 若选第i种货币：需满足j >= 当前货币面值coin，且组成j-coin的最少货币数已知（非无穷大），此时dp[i][j] = dp[i][j-coin] + 1（用组成j-coin的最少货币数加1张当前货币）；
• 最终取两种选择中的较小值作为dp[i][j]的最优解。

二、状态转移方程讲解

1. 状态定义

dp[i][j]：使用前i种货币组成金额j所需的最少货币数。

2. 初始化

• dp[i][0] = 0（组成金额0无需任何货币，最少数量为0）；
• dp[0][j] = INT_MAX（不使用任何货币时，除金额0外，其他金额无法组成，用无穷大表示无解）。

3. 状态转移

• 不选第i种货币：dp[i][j] = dp[i-1][j] 解释：直接沿用前i-1种货币组成金额j的最少货币数。
• 选第i种货币（需满足j >= coin且dp[i][j-coin] ≠ INT_MAX）：dp[i][j] = min(dp[i][j], dp[i][j-coin] + 1) 解释：用前i种货币组成j-coin的最少货币数加1张当前货币，与不选当前货币的结果取较小值。

4. 最终结果

若dp[n][aim] = INT_MAX，说明无法组成aim，返回-1；否则返回dp[n][aim]。

三、核心逻辑总结

该解法基于完全背包思想（每种货币可重复使用），通过动态规划逐步扩展货币种类和金额，利用子问题的最优解推导更大问题的最优解。状态转移的关键是“选或不选当前货币”的二选一决策，确保每一步都保留最少货币数的最优解。

四、完整代码

#include <algorithm>
#include <climits>
#include <vector>
class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {
        int n = arr.size();
        vector<vector<int>>dp(n+1,vector<int>(aim+1,INT_MAX));
	  //初始化，凑0元需要0张任意面值的货币
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for(int i = 1;i <= n; i++){
            int coin = arr[i-1];
            for(int j = 1;j <= aim;j++){
                int targe = j;
                // 注意边界处理
                dp[i][j] = dp[i-1][j];
                if(targe>=coin && dp[i][j-coin]!=INT_MAX){
                    dp[i][j] = min(dp[i][j-coin]+1, dp[i-1][j]);
                }
            }
        }
        return dp[n][aim]==INT_MAX?-1:dp[n][aim];
    }
};