c++题解 | #兑换零钱#

解释下这种状态转移的思路： dp[i]表示组成i的最少货币数，那对于一种状态dp[k]，就表示组成k的最少货币数状态，它可以来自于两个方面：

1. 遍历每个货币，当k>=arr[i]就可以来自于dp[k-arr[i]]这个状态，表示组成{k-arr[i]}的最少货币数再加上arr[i]这种货币1个就到了dp[k]；
2. 上面那种状态的计算的值比本来自己的值（最少货币数）还大，就不更新了，保持原状态。
   至于想象中是否需要考虑每种货币的数量，其实在更新较小的状态时就保存了数量的信息。
   比如arr={2,5}, aim = 6, dp[6]可以来自dp[4]和dp[1]（一定是INT_MAX）, dp[4]可以来自于dp[2],那dp[4]一定是2，对应的dp[6]就是dp[4]+1=3

#include <cstdio>
#include <iostream>
#include <limits.h>
using namespace std;
const int N = 10010;
const int M = 5001;
int dp[N];  //dp[i]表示组成i的最少货币数
int arr[N];
int main() {
    int n, aim;
    scanf("%d %d", &n, &aim);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 0; i < M; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    for (int j = 1; j <= aim; j++) {
        for (int i = 1; i <= n; i++) {
            if (arr[i] <= j) {
                dp[j] = min(dp[j - arr[i]] + 1, dp[j]);
            }
        }
    }
    if(dp[aim] == INT_MAX)
        printf("-1");
    else
        printf("%d", dp[aim]);


    return 0;
}

也可以将转移方程改为下面这种形式，思路是：用dp[j]可以更新谁，如果实现了更新，一定更新的是dp[j+arr[i]]

    for (int j = 0; j <= aim; j++) {
        for (int i = 1; i <= n; i++) {
            dp[j+arr[i]] = min(dp[j]+1, dp[j+arr[i]]);
        }
    }