【CSES】1634. Minimizing Coins

題目連結

時間複雜度

• $O(N)$

解題想法

一看題目就知道這題是很水的 DP 題，所以想當然在解的時候就直接 DP Bottom-Up 就可以快樂的 AC 掉了

但這邊有一個值得注意的地方就是如何判斷是否有解，我當初在測試的時候有稍微卡了一下下，因為我原本想說如果等於我預設的最大值的話就直接輸出無解，但後來發現這樣行不通，因為有時候答案可能剛好就是預設的最大值😅，對此我換了一個寫法

我把它寫成 if( i == x && dp[i-coins[j]] + 1 < dp[i] ) 這樣的話只有當

$i=x$ 且可以 Update dp 裡面的值的時候我才正常輸出（因為可以 Update 就代表這個值至少有一組解），否則無解，這樣一來就可以正常判斷答案了

完整程式

/* Question : OJ Number */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e6 + 50;
const int Mod = 1e9 + 7;
int n, x, coins[MAXN], dp[MAXN];
bool flag = false;

signed main(){
    opt;
    cin >> n >> x;
    for( int i = 0 ; i < n ; i++ ) cin >> coins[i];
    mem(dp);
    dp[0] = 0;
    for( int i = 1 ; i <= x + 5 ; i++ ){
        for( int j = 0 ; j < n ; j++ ){
            if( i - coins[j] < 0 ) continue;
            if( i == x && dp[i-coins[j]] + 1 < dp[i] ) flag = true;
            dp[i] = min(dp[i], dp[i-coins[j]] + 1);
        }
    }
    if( flag == false ) cout << "-1\n";
    else cout << dp[x] << "\n";
}