Base: dp[0] = 0
O(n)
1dp[0], dp[1] = 0, 12for i in range(2, n+1):3 dp[i] = dp[i-1] + dp[i-2]4return dp[n]