Solving a Question with Dynamic Programming

▸
1def rob(nums):
2    # 1. state:      dp[i] = best loot using houses 0..i
3    # 2. recurrence: dp[i] = max(dp[i−1], dp[i−2] + nums[i])
4    # 3. base cases:
5    dp[0] = nums[0]
6    dp[1] = max(nums[0], nums[1])
7    # 4. order: left to right
8    for i in 2..n−1:
9        # skip house i, or rob it + best two back
10        dp[i] = max(dp[i−1], dp[i−2] + nums[i])
11    # 5. answer lives in the last cell
12    return dp[n−1]