Are you sure you're getting this? Fill in the missing part by typing it in.
In the dynamic programming solution for the coin change problem, we create an array dp
of size amount + 1
and initialize all its values to _____________
, except for dp[0]
which is set to 0
since we don't need any coins to make zero change.
We then iterate from 1
to amount
and for each value i
, we iterate through the coins
array. If the current coin coin
is less than or equal to i
, we update dp[i]
to be the minimum between its current value and dp[i - coin] + 1
. This represents the minimum number of coins needed to make the amount i
using the current coin and any previously calculated solutions.
Finally, we return dp[amount]
, which will be the minimum number of coins needed to make the given amount of change. If dp[amount]
is greater than amount
, it means that it was not possible to make the amount using the given coins, so we return -1
.
Fill in the blank with the correct value for initializing the dp
array.
Write the missing line below.