Template: 10. DYNAMIC PROGRAMMING — 1D Template

10. DYNAMIC PROGRAMMING — 1D Template

# =============================================================================
def dp_1d(n):
    # Step 1: Define state — dp[i] = "..."
    dp = [0] * (n + 1)

    # Step 2: Base cases
    dp[0] = 1  # adjust per problem

    # Step 3: Fill table (recurrence)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1]  # + dp[i-2] etc. — adjust per problem

    # Step 4: Return answer
    return dp[n]


# =============================================================================