DPL_1_A:Coin Changing Problem [动态规划]

题目链接

现在给了m枚不同面值的硬币,要求用最少的硬币凑出n元钱,求出所需要的最少的硬币的数量;

用动态规划来做,现在用:

dp[i][j]=x d p [ i ] [ j ] = x 表示现在用第1-i枚硬币,凑出价值为j的钱需要的最少的硬币数量为x;

可以想到:

dp[i][j]=min(dp[i−1][j],dp[i][j−c[i]]+1) d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − c [ i ] ] + 1 )

想到,其实不需要保存i这个变量,只需要使用dp[j]就可以了:

dp[i]=min(dp[i],dp[i−c[j]]+1) d p [ i ] = m i n ( d p [ i ] , d p [ i − c [ j ] ] + 1 )

伪代码如此:

for(i from  to m)
    for(j from c[i] to n)
        dp[j]=min(dp[j],dp[j-c[i]]);
           

初始化的时候有2点:

1.不论用多少硬币凑出0元都只需要0个硬币;

2.用0个硬币凑出大于0元的价值都需要INF的硬币;

最后代码如此:

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=;
const int maxm=+;
const int INF=;

int c[maxm],dp[maxn];
int n,m;

int main (){
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=;i<=m;i++){
        cin>>c[i];
    }
    dp[]=;
    for(int i=;i<=n;i++){
        dp[i]=INF;
    }
    for(int i=;i<=m;i++){
        for(int j=c[i];j<=n;j++){
            dp[j]=min(dp[j],dp[j-c[i]]+);
        }
    }
    cout<<dp[n]<<endl;
    return ;
}

           

错点:

1.一开始我一直在考虑可能有些价值凑不出来的问题,忽略了题目里有限制条件

The denominations are all different and contain 1.

所以所有价值都是可以凑出来的;

2.初始化条件要注意上面的2点;