Build your intuition. 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.