1.题目描述

今有面值为 1、5、11 元的硬币各无限枚。
想要凑出 九 元，问需要的最少硬币数量。

2.输入格式

仅一行，一个正整数 n。

3.输出格式

仅一行，一个正整数，表示需要的硬币个数。

4.输入输出样例

1.输入1：

15

2.输出1：

3

3.输入2：

12

4.输出2：

2

5.说明/提示

样例解释
对于样例数据 1，最佳方案是 15 =5+5 +5，使用到3 枚硬币。对于样例数据 2，最佳方案是 12 = 11 + 1，使用到 2 枚硬币。数据规模与约定
对于 100% 的数据，保证n <= 10^6

6.代码：

#include <stdio.h>
#include <limits.h>#define MAX_N 1000000int main() {int n;scanf("%d", &n);int dp[MAX_N + 1];// 初始化for (int i = 0; i <= n; i++) {dp[i] = INT_MAX; // 设置为一个很大的数}dp[0] = 0; // 凑成0元所需的硬币数为0// 硬币面值int coins[] = {1, 5, 11};int coinCount = sizeof(coins) / sizeof(coins[0]);// 动态规划过程for (int i = 1; i <= n; i++) {for (int j = 0; j < coinCount; j++) {if (i - coins[j] >= 0) {dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;}}}printf("%d\n", dp[n]);return 0;
}