Coin Change Problem (Dynamic Programming)

youtube
I've asked to chatGPT why dp[i] +=dp[i-coin]

In point 2), we consider the case where we use the coin c to make change for the amount i. In this case, we can use the same number of possible combinations as we could for the amount i-c to make change for the amount i. Let me give you an example to illustrate this. Suppose we have the coins [1, 2, 5] and we want to make change for the amount 7. To compute the number of possible combinations of coins required to make change for the amount 7 using the coins up to 5, we can do the following: We start with dp[0] = 1, since there is only one way to make change for 0 (using no coins). We consider the first coin 1. For each amount i from 1 to 7, we check whether we can use the coin 1 to make change for the amount i. If we can, we update dp[i] by adding the value of dp[i-1] to it, since we can use one 1 coin and the number of possible combinations required to make change for the amount i-1 to make change for the amount i. For example, to make change for the amount 2, we can use one 1 coin and the number of possible combinations required to make change for the amount 1. Therefore, we update dp[2] by adding dp[1] to it. After considering the first coin, we have dp = [1, 1, 1, 1, 1, 1, 1]. We consider the second coin 2. For each amount i from 2 to 7, we check whether we can use the coin 2 to make change for the amount i. If we can, we update dp[i] by adding the value of dp[i-2] to it, since we can use one 2 coin and the number of possible combinations required to make change for the amount i-2 to make change for the amount i. For example, to make change for the amount 3, we can use one 2 coin and the number of possible combinations required to make change for the amount 1. Therefore, we update dp[3] by adding dp[1] to it. After considering the second coin, we have dp = [1, 1, 2, 2, 3, 3, 4]. We consider the third coin 5. For each amount i from 5 to 7, we check whether we can use the coin 5 to make change for the amount i. If we can, we update dp[i] by adding the value of dp[i-5] to it, since we can use one 5 coin and the number of possible combinations required to make change for the amount i-5 to make change for the amount i. For example, to make change for the amount 6, we can use one 5 coin and the number of possible combinations required to make change for the amount 1. Therefore, we update dp[6] by adding dp[1] to it. After considering the third coin, we have dp = [1, 1, 2, 2, 3, 4, 5].