House Robber - Solution & Explanation

This approach uses a dynamic programming table, where we maintain an array 'dp' such that dp[i] represents the maximum amount of money that can be robbed up to house i. We iterate through the list of houses and for each house, decide whether to rob it or skip it, based on the previous results stored in the dp table.

This solution defines a 'dp' array where each entry at index 'i' stores the maximum money that can be robbed from the first 'i+1' houses. At each house, you choose the maximum value between not robbing the current house or robbing it and adding its value to the maximum of all the previous non-adjacent houses.

This approach optimizes the space complexity by not using a separate array for storing results of subproblems. Instead, we use two variables to keep track of the maximum amount that can be robbed up to the last two houses considered. This eliminates the need for an auxiliary array and reduces space complexity to O(1).

This C implementation contains no dp array but uses 'prev1' and 'prev2' variables to keep track of the maximum amounts robbed from the last house considered and the second last house, respectively. The current variable is updated each iteration.

We design a function dfs(i), which represents the maximum amount of money that can be stolen starting from the i-th house. Thus, the answer is dfs(0).

The execution process of the function dfs(i) is as follows:

• If i \ge len(nums), it means all houses have been considered, and we directly return 0;
• Otherwise, consider stealing from the i-th house, then dfs(i) = nums[i] + dfs(i+2); if not stealing from the i-th house, then dfs(i) = dfs(i+1).
• Return max(nums[i] + dfs(i+2), dfs(i+1)).

To avoid repeated calculations, we use memoization search. The result of dfs(i) is saved in an array or hash table. Before each calculation, we first check if it has been calculated. If so, we directly return the result.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.

We define f[i] as the maximum total amount that can be robbed from the first i houses, initially f[0]=0, f[1]=nums[0].

Consider the case where i \gt 1, the ith house has two options:

• Do not rob the ith house, the total amount of robbery is f[i-1];
• Rob the ith house, the total amount of robbery is f[i-2]+nums[i-1];

Therefore, we can get the state transition equation:

$ f[i]= \begin{cases} 0, & i=0 \ nums[0], & i=1 \ max(f[i-1],f[i-2]+nums[i-1]), & i \gt 1 \end{cases}

The final answer is f[n], where n is the length of the array.

The time complexity is O(n), and the space complexity is O(n). Where n$ is the length of the array.

We notice that when i \gt 2, f[i] is only related to f[i-1] and f[i-2]. Therefore, we can use two variables instead of an array to reduce the space complexity to O(1).