I was solving minimising coins problem on CSES. I was successfully able to solve.
My solution has two for loops.
The outer for loop runs over the sums from 1 to x
The inner loop iterates over coins
vector<int> dp(x + 1);
dp[0] = 0;
for (int i = 1; i <= x; i++)
{
int ans = INT_MAX;
for (int coin : coins)
{
if (i - coin >= 0 and dp[i - coin] >= 0)
{
ans = min(ans, 1 + dp[i - coin]);
}
}
dp[i] = (ans == INT_MAX ? -1 : ans);
}
cout << dp[x] << endl;
But in the editorial on USACO guide
The outer for loop runs over the coins
The inner loop iterates over target sum from 0 to x
int main() {
int n, x;
cin >> n >> x;
vi coins(n);
for (int i = 0; i < n; i++) { cin >> coins[i]; }
for (int i = 0; i <= x; i++) { dp[i] = INT_MAX; }
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int weight = 0; weight <= x; weight++) {
if (weight - coins[i - 1] >= 0) {
dp[weight] = min(dp[weight], dp[weight - coins[i - 1]] + 1);
}
}
}
cout << (dp[x] == INT_MAX ? -1 : dp[x]) << '\n';
}
Can someone help me in wrapping my head around the second approach. I am unable to figure how can the second approach also work correctly.