Dinamik dasturlash

Dinamik dasturlash (DP): katta masalaning javobini kichik masalalar javobidan yig‘ish va har birini bir marta hisoblash.

1. Holat: dp[i] nimani bildiradi? (masalan, i summani to‘lash uchun eng kam tanga)
2. O‘tish: dp[i] = min(dp[i - c] + 1 for c in coins)
3. Boshlang‘ich: dp[0] = 0
4. Javob: dp[n]

INF = float("inf")
dp = [0] + [INF] * n
for i in range(1, n + 1):
    for c in coins:
        if c <= i:
            dp[i] = min(dp[i], dp[i - c] + 1)

Zinapoya masalasi — eng oddiy DP: dp[i] = dp[i-1] + dp[i-2].