DP: states, transitions, order and reconstruction

DP is a problem model, not merely a cache trick. Define each state exactly, derive transitions from the final decision, and specify base/impossible states. Tabulation needs dependency order; memoisation visits only reached states.

Minimum coins uses dp[0]=0 and dp[x]=min(dp[x−c]+1), with positive coins. The optimum count does not reveal selected coins; retain choices for reconstruction.

State must preserve all information needed by future decisions. Analyse number of states times transition cost. Knapsack O(nW) is pseudo-polynomial in numeric capacityW rather than polynomial in its encoded bit length.

Make the DP state explicit

For coins {1,3,4} and target six, greedy selects 4+1+1, using three coins. The optimum is 3+3. Let dp[x] mean the minimum coins for exactly x. Set dp[0]=0 and initialise other states to +∞. Transition dp[x]=min(dp[x−c]+1) for c≤x. Increasing x ensures dependencies are ready; unreachable states remain infinite.

x	0	1	2	3	4	5	6
dp[x]	0	1	2	1	1	2	2

Store the selected coin in parent[x] to reconstruct a solution by walking back to zero. A tie-break rule makes output deterministic. Returning a count differs from returning a witness.

Correctness requires a state that captures optimal substructure. Ask which past information future choices need. Single-use coins require a different transition from unlimited coins. In one-dimensional 0/1 knapsack, the wrong capacity-loop direction can reuse one item.

Foundation: Derive dp[6]. Intermediate: Reconstruct the coin list. Advanced: Explain why O(target·k) is pseudo-polynomial when target is binary-encoded; specify unreachable amounts and zero/negative coin contracts.

def min_coins(coins, target):
    if target < 0 or any(c <= 0 for c in coins): raise ValueError("invalid input")
    dp = [0]+[float("inf")]*target
    for x in range(1,target+1):
        for c in coins:
            if c <= x: dp[x]=min(dp[x],1+dp[x-c])
    return None if dp[target] == float("inf") else dp[target]
assert min_coins([1,3,4],6) == 2