首页 > 试题广场 >

硬币凑钱

[编程题]硬币凑钱
  • 热度指数：227 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt} 银行拥有面值为 7 元、5 元与 1 元的硬币若干，每种面值的硬币数量均视为无限。现在需要支付恰好 n 元，求出所需硬币数量的最小值。

输入描述:
\hspace{15pt} 在一行上输入一个整数 n\left(1\leqq n\leqq 10^6\right)，表示需要支付的金额（单位：元）。


输出描述:
\hspace{15pt} 输出一个整数，表示凑成 n 元所需的最少硬币数量。
示例1

输入

8

输出

2

说明

该样例中，可选择一枚 7 元硬币与一枚 1 元硬币，支付 7+1=8 元，共使用 2 枚硬币。无法使用更少的硬币凑成 8 元。
示例2

输入

10

输出

2

说明

该样例中，可选择两枚 5 元硬币，支付 5+5=10 元，共使用 2 枚硬币。
算法知识视频讲解
添加回答
牛客756881142号头像 牛客756881142号
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int dp[n + 1];
    for (int i = 0; i < n + 1 ; i++) {
        dp[i] = i;
    }

    for (int i = 1; i < n + 1; i++) {
        if (i >= 1) {
            dp[i] = dp[i] < (dp[i-1] +1)?dp[i] : (dp[i-1] +1);
        }
        if (i >= 5) {
            dp[i] = dp[i] < (dp[i-5] +1)?dp[i] : (dp[i-5] +1);
        }
        if (i >= 7) {
            dp[i] = dp[i] < (dp[i-7] +1)?dp[i] : (dp[i-7] +1);
        }
    }
    printf("%d",dp[n]);

    return 0;
}
发表于 2025-07-13 14:46:37 回复(0)
提交观点

问题信息

难度：
1条回答 11浏览

热门推荐

相关试题

硬币凑钱

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号