Overlapping Subproblems and Optimal Substructure

Define a state whose answer can be reused

Dynamic programming is useful when subproblems overlap and optimal answers can be assembled from smaller optimal answers. The state must include all information needed by future decisions.

Copy codefun minCoins(amount: Int, coins: IntArray): Int? {
    require(amount in 0..100_000 && coins.all { it > 0 })
    val unreachable = amount + 1
    val dp = IntArray(amount + 1) { unreachable }
    dp[0] = 0
    for (value in 1..amount) {
        for (coin in coins) if (coin <= value) {
            dp[value] = minOf(dp[value], dp[value - coin] + 1)
        }
    }
    return dp[amount].takeIf { it != unreachable }
}

The chosen bound keeps allocation and sentinel arithmetic manageable for this lesson. Time is O(amount × coin count), space O(amount). Coins may be reused without limit; a one-use-per-coin problem needs a different state or iteration policy.

Exercise

Verify target six with [1,3,4], an unreachable odd target with [2], and zero with no coins.

Check: explain why the zero state is reachable with zero coins while other states initially are not.

Further reading: Optimization problems