House robber

Pick values from a row so that no two picks are next to each other, and the total is as large as possible.

The idea

dp[i] is the best total using the first i houses. For house i there are two choices: skip it and keep dp[i-1], or take it and add its value to dp[i-2].

Code

int rob(const vector<int>& a) {
    vector<int> dp(a.size() + 1, 0);
    dp[1] = a[0];
    for (int i = 2; i <= (int)a.size(); i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 1]);
    return dp[a.size()];
}

def rob(a: list[int]) -> int:
    dp = [0] * (len(a) + 1)
    dp[1] = a[0]
    for i in range(2, len(a) + 1):
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 1])
    return dp[len(a)]

public static int Rob(int[] a) {
    var dp = new int[a.Length + 1];
    dp[1] = a[0];
    for (int i = 2; i <= a.Length; i++)
        dp[i] = Math.Max(dp[i - 1], dp[i - 2] + a[i - 1]);
    return dp[a.Length];
}

Tips

• This "take it or skip it" choice is the heart of many DP problems, including knapsack.
• Simply taking every other house fails. Sometimes the best plan skips two houses in a row to reach a big one.

In the .NET library

Math.Max makes the take-or-skip choice one expression. As with climbing stairs, two variables can replace the array.