Dynamic Programming

1// 1D DP space-optimized to O(1)
2int linearDP(int n)
3{
4    if (n <= 1) return n;
5 
6    int prev2 = 0;   // state for dp[i-2]
7    int prev1 = 1;   // state for dp[i-1]
8    int cur   = 0;   // state for dp[i]
9 
10    for (int i = 2; i <= n; i++)
11    {
12        // Example transition: dp[i] = dp[i-1] + dp[i-2]
13        cur   = prev1 + prev2;
14        prev2 = prev1;
15        prev1 = cur;
16    }
17 
18    return cur;
19}