An interactive visualization of how dynamic programming finds the minimum number of coins needed to make a target amount. Watch the algorithm build up solutions from smaller subproblems.
Dynamic Programming LeetCode 322 ↗ Mediumcoins representing coins of different denominations and an integer amount representing a total amount of money, return the fewest number of coins that you need to make up that amount.-1.fun coinChange(coins: IntArray, amount: Int): Int { val dp = IntArray(amount + 1) { Int.MAX_VALUE } dp[0] = 0 // base case for (i in 1..amount) { for (coin in coins) { if (coin <= i && dp[i - coin] != Int.MAX_VALUE) { dp[i] = minOf(dp[i], dp[i - coin] + 1) return if (dp[amount] == Int.MAX_VALUE) -1 else dp[amount]
The minimum number of coins to make amount i can be found by trying each coin and taking
the minimum of dp[i - coin] + 1 for all coins that don't exceed i.
This builds up the solution from smaller amounts to the target amount.
amount + 1, filled with infinity. Set dp[0] = 0 (base case: zero coins needed for amount 0).dp[i - coin] + 1 (use one coin and add the solution for the remaining amount).dp[i] with the minimum of its current value and the new calculation.dp[amount] is still infinity, return -1 (impossible). Otherwise, return dp[amount].We iterate through all amounts from 1 to the target, and for each amount, we try all coin denominations. This gives us O(amount × coins) time complexity. The space complexity is O(amount) for the DP array.