#include<stdio.h> int dp[1000001]; int coins[3]={1,5,11}; int main() { int n,coin; scanf("%d",&n); int dp[1000001]; for(int i=0;i<n;i++) dp[i]=1000001; dp[0]=0; for(int i=0;i<n;i++) { for(int j=0;j<3;j++) { coin=coins[j]; if(i-coin>=0) { if(dp[i]<(1+dp[i-coin])) dp[i]=dp[i]; else dp[i]=1+dp[i-coin]; } } } return (dp[n]==1000001)?-1:dp[n]; }

这是一个使用动态规划思想解决硬币找零问题的程序。假设要找n元的零钱，coins数组保存了可用的硬币面额，dp[i]表示找i元钱所需的最少硬币数。

程序首先读入n，然后初始化dp数组，将所有元素设为一个较大的值（1000001），除了dp[0]为0，因为找0元钱不需要硬币。

接着，程序从1元开始逐个计算dp[i]，对于每个dp[i]值，它可以由dp[i-coin]加上一个面额为coin的硬币得到，其中coin取值为1、5、11。因此，程序循环遍历coins数组，对于每个coin，如果i-coin>=0，说明可以用一个coin硬币得到dp[i]，那么就比较dp[i]和dp[i-coin]+1哪个更小，取最小值作为dp[i]的值。

最后，如果dp[n]仍为初始值1000001，说明无法找零，程序返回-1，否则返回dp[n]，即找n元钱所需的最少硬币数。

相关问题

#include<stdio.h> int dp[1000001]={1000001}; int coins[3]={1,5,11}; int main() { int n,coin; scanf("%d",&n); dp[0]=0; for(int i=0;i<n;i++) { for(int j=0;j<3;j++) { coin=coins[j]; if(i-coin<0) continue; } if(dp[i]<(1+dp[i-coin])) dp[i]=dp[i]; else dp[i]=1+dp[i-coin]; } return(dp[n]==n+1)?-1:dp[n]; }

这是一个使用动态规划解决找零钱问题的代码，但是有一些错误。

首先，在定义 dp 数组时，应该初始化为最大值，而不是只初始化第一个元素为最大值。可以改为：

int dp[1000001];
for(int i = 0; i <= n; i++){
    dp[i] = 1000001;
}

其次，在第二个 for 循环中，应该将花费硬币的操作放在循环内部，而不是循环外部。可以改为：

for(int j=0;j<3;j++) {
    coin=coins[j];
    if(i-coin>=0) {
        if(dp[i]<(1+dp[i-coin]))
            dp[i]=dp[i];
        else
            dp[i]=1+dp[i-coin];
    }
}

最后，在返回结果时，应该判断 dp[n] 是否等于初始值，而不是 n+1，因为当 n=0 时，n+1 会等于 1，而 dp[0] 初始值为 0。可以改为：

return (dp[n]==1000001)?-1:dp[n];

修改后的完整代码如下：

#include<stdio.h>
int dp[1000001];
int coins[3]={1,5,11};

int main() {
    int n, coin;
    scanf("%d",&n);
    for(int i = 0; i <= n; i++){
        dp[i] = 1000001;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<3;j++) {
            coin=coins[j];
            if(i-coin>=0) {
                if(dp[i]<(1+dp[i-coin]))
                    dp[i]=dp[i];
                else
                    dp[i]=1+dp[i-coin];
            }
        }
    }
    return (dp[n]==1000001)?-1:dp[n];
}

#include<stdio.h> int dp[1000001]; int coins[3]={1,5,11}; int main() { int n,coin; scanf("%d",&n); int dp[1000001]; for(int i=0;i<=n;i++) dp[i]=1000001; dp[0]=0; for(int i=0;i<=n;i++) { for(int j=0;j<3;j++) { coin=coins[j]; if(i-coin>=0) { if(dp[i]<(1+dp[i-coin])) dp[i]=dp[i]; else dp[i]=1+dp[i-coin]; } } } printf("%d",dp[n]); return 1; }

这是一个使用动态规划算法解决硬币找零问题的代码。硬币找零问题指的是，给定一些不同面额的硬币和一个总金额，找出来组成该总金额所需的最少硬币数。

这段代码中，dp数组表示组成金额i所需的最少硬币数。coins数组表示给定的不同面额的硬币。代码的主要思路是对于每个金额i，枚举硬币面额j，然后尝试使用硬币j来组成金额i，更新dp[i]的值。

具体来说，对于每个金额i，我们枚举硬币面额j，计算使用硬币j组成金额i所需的最少硬币数。如果使用硬币j可以组成金额i，并且使用硬币j组成金额i所需的硬币数比当前的dp[i]所需的硬币数更少，那么就更新dp[i]的值。

最后，输出dp[n]，即为组成总金额n所需的最少硬币数。