My DP solution with explanation


  • 2
    A

    Dp solution, O(n) space ,O(n) time.
    create a vector Dp, where Dp[i] = max(Dp[i-1], Dp[i-2]+num[i]). Because there are two choices,rob ith house or not,and they are two subproblems, so Dp solution is effective.

    class Solution {
        public:
            int rob(vector<int> &num) {
                int len = num.size();     
            	if( len == 0 )
            		return 0;
            	vector<int> Dp(len,0);
            	Dp[0] = num[0];
            	for( int i = 1; i < len; i++ )
            		Dp[i] = max(Dp[i-1], i-2 >= 0 ? Dp[i-2] + num[i]:num[i]);
            	return Dp[len-1];
            }
        };

  • 0
    A
    This post is deleted!

  • 1
    A

    O(1) space solution

    class Solution {
        public:
            int rob(vector<int> &num) {
                int len = num.size();
            	if( len == 0 )
            		return 0;
            	int f1 = num[0],f2 = 0;
            	for( int i = 1; i < len; i++ )
            	{
            		f2 = max(f1, num[i]+ f2);
            		swap( f1, f2 );
            	}
            	return f1;
            }
        };

  • 1
    C
    public int rob(int[] num) {
        int n = num.length;
        if(n == 0) return 0;
        int[] max = new int[n + 2];
        max[0] = 0;
        max[1] = 0;
        max[2] = num[0];
        for(int i = 1; i < n; i++) {
            max[i + 2] = Math.max(max[i], max[i - 1]) + num[i];
        }
        return Math.max(max[n], max[n + 1]);
    }
    

    When we traverse houses, we use a array to record the max we can rob until the last rob house. So max[i] =( max[i - 2], max[i -3]) + num[i], we must choose one from the previous three houses.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.