Find maximum possible stolen value from houses Dynamic Programming(Top-Down Approach)

Find the maximum possible stolen value from houses using O(n) extra space

Find maximum possible stolen value from houses Dynamic Programming(Bottom Up Approach):

The sub-problems can be stored thus reducing the complexity and converting the recursive solution to a Dynamic programming problem.

Follow the below steps to Implement the idea:

Create a DP vector of size n+1 and value -1 and variables pick and not pick.
Create a recursive function
- If n < 0 possible stolen value is 0.
- If n = 0 possible stolen value is hval[0].
- If DP[n] != -1 possible stolen value is DP[n].
- Set pick as pick = hval[n] + maxLoot(hval, n-2, DP)
- Set not pick as notPick = maxLoot(hval, n-1, DP).
- Set Dp[n] = max(pick, notPick) and return DP[n].

Below is the Implementation of the above approach:

C++

// CPP program to find the maximum stolen value 
#include <bits/stdc++.h> 
using namespace std; 
  
// calculate the maximum stolen value 
int maxLoot(int *hval, int n, vector<int> &dp){ 
    
   // base case 
   if(n < 0){ 
           return 0 ; 
   } 
     
   if(n == 0){ 
           return hval[0] ; 
   } 
   // If the subproblem is already solved 
   // then return its value 
   if(dp[n] != -1 ){ 
          return dp[n] ; 
   } 
    
   //if current element is pick then previous cannot be picked 
   int pick = hval[n] +  maxLoot(hval, n-2, dp) ; 
   //if current element is not picked then previous element is picked 
   int notPick = maxLoot(hval, n-1, dp)  ; 
    
   // return max of picked and not picked 
   return dp[n] = max(pick, notPick) ; 
    
} 
  
// Driver to test above code 
int main() 
{ 
    int hval[] = {6, 7, 1, 3, 8, 2, 4}; 
    int n = sizeof(hval)/sizeof(hval[0]); 
    // Initialize a dp vector 
    vector<int> dp(n+1, -1) ; 
    cout << "Maximum loot possible : "
        << maxLoot(hval, n-1, dp); 
    return 0; 
} 

Java

/*package whatever //do not write package name here */
  
// Java program to find the maximum stolen value 
import java.io.*; 
import java.util.Arrays; 
  
class GFG { 
  // Function to calculate the maximum stolen value 
  static int maxLoot(int hval[], int n, int dp[]) 
  { 
    // base case 
    if (n < 0) { 
      return 0; 
    } 
  
    if (n == 0) { 
      return hval[0]; 
    } 
    // If the subproblem is already solved 
    // then return its value 
    if (dp[n] != -1) { 
      return dp[n]; 
    } 
  
    // if current element is pick then previous cannot 
    // be picked 
    int pick = hval[n] + maxLoot(hval, n - 2, dp); 
    // if current element is not picked then previous 
    // element is picked 
    int notPick = maxLoot(hval, n - 1, dp); 
  
    // return max of picked and not picked 
    return dp[n] = Math.max(pick, notPick); 
  } 
  
  // Driver program 
  public static void main(String[] args) 
  { 
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 }; 
    int n = hval.length; 
    int dp[] = new int[n + 1]; 
    Arrays.fill(dp, -1); 
    System.out.println("Maximum loot possible : "
                       + maxLoot(hval, n - 1, dp)); 
  } 
} 
  
// This code is contributed by sanskar84.

Python3

# Python3 program to find the maximum stolen value 
  
# calculate the maximum stolen value 
  
  
def maxLoot(hval, n, dp): 
  
    # base case 
    if(n < 0): 
        return 0
  
    if(n == 0): 
        return hval[0] 
  
   # If the subproblem is already solved 
   # then return its value 
    if(dp[n] != -1): 
        return dp[n] 
  
    # if current element is pick then previous cannot be picked 
    pick = hval[n] + maxLoot(hval, n-2, dp) 
  
    # if current element is not picked then previous element is picked 
    notPick = maxLoot(hval, n-1, dp) 
  
    # return max of picked and not picked 
    dp[n] = max(pick, notPick) 
    return dp[n] 
  
  
# Driver to test above code 
hval = [6, 7, 1, 3, 8, 2, 4] 
n = len(hval) 
  
# Initialize a dp vector 
dp = [-1 for i in range(n+1)] 
print("Maximum loot possible : "+str(maxLoot(hval, n-1, dp))) 
  
# This code is contributed by shinjanpatra 

C#

// C# program to find the maximum stolen value 
using System; 
public class GFG { 
  
    // Function to calculate the maximum stolen value 
    static int maxLoot(int[] hval, int n, int[] dp) 
    { 
        
        // base case 
        if (n < 0) { 
            return 0; 
        } 
  
        if (n == 0) { 
            return hval[0]; 
        } 
        // If the subproblem is already solved 
        // then return its value 
        if (dp[n] != -1) { 
            return dp[n]; 
        } 
  
        // if current element is pick then previous cannot 
        // be picked 
        int pick = hval[n] + maxLoot(hval, n - 2, dp); 
        
        // if current element is not picked then previous 
        // element is picked 
        int notPick = maxLoot(hval, n - 1, dp); 
  
        // return max of picked and not picked 
        return dp[n] = Math.Max(pick, notPick); 
    } 
  
    static public void Main() 
    { 
  
        // Code 
        int[] hval = { 6, 7, 1, 3, 8, 2, 4 }; 
        int n = hval.Length; 
        int[] dp = new int[n + 1]; 
        Array.Fill(dp, -1); 
        Console.WriteLine("Maximum loot possible : "
                          + maxLoot(hval, n - 1, dp)); 
    } 
} 
  
// This code is contributed by lokeshmvs21.

Javascript

<script> 
  
// JavaScript program to find the maximum stolen value 
  
// calculate the maximum stolen value 
function maxLoot(hval,n,dp){ 
    
   // base case 
   if(n < 0){ 
        return 0 ; 
   } 
     
   if(n == 0){ 
        return hval[0] ; 
   } 
   // If the subproblem is already solved 
   // then return its value 
   if(dp[n] != -1 ){ 
        return dp[n] ; 
   } 
    
   //if current element is pick then previous cannot be picked 
   let pick = hval[n] +  maxLoot(hval, n-2, dp) ; 
   //if current element is not picked then previous element is picked 
   let notPick = maxLoot(hval, n-1, dp)  ; 
    
   // return max of picked and not picked 
   return dp[n] = Math.max(pick, notPick) ; 
    
} 
  
// Driver to test above code 
let hval = [6, 7, 1, 3, 8, 2, 4]; 
let n = hval.length; 
// Initialize a dp vector 
let dp = new Array(n+1).fill(-1) ; 
document.write("Maximum loot possible : ",maxLoot(hval, n-1, dp),"</br>"); 
// code is contributed by shinjanpatra 
  
</script>

Output

Maximum loot possible : 19

Time Complexity: O(n). Only one traversal of the original array is needed. So the time complexity is O(n)
Space Complexity: O(n). Recursive stack space is required of size n, so space complexity is O(n).

Find maximum possible stolen value from houses (House Robber)

There are N houses built in a line, each of which contains some value in it. A thief is going to steal the maximum value of these houses, but he can’t steal in two adjacent houses because the owner of the stolen houses will tell his two neighbors left and right sides. The task is to find what is the maximum stolen value.

Examples:

Input: hval[] = {6, 7, 1, 3, 8, 2, 4}
Output: 19
Explanation: The thief will steal 6, 1, 8 and 4 from the house.

Input: hval[] = {5, 3, 4, 11, 2}
Output: 16
Explanation: Thief will steal 5 and 11

Naive Approach: Below is the idea to solve the problem:

Given an array, the solution is to find the maximum sum subsequence where no two selected elements are adjacent. So the approach to the problem is a recursive solution.

So there are two cases:

If an element is selected then the next element cannot be selected.

if an element is not selected then the next element can be selected.

Use recursion to find the result for both cases.

Below is the Implementation of the above approach:

C++

// CPP program to find the maximum stolen value 
#include <iostream> 
using namespace std; 
  
// calculate the maximum stolen value 
int maxLoot(int* hval, int n) 
{ 
    // base case 
    if (n < 0) { 
        return 0; 
    } 
  
    if (n == 0) { 
        return hval[0]; 
    } 
    // if current element is pick then previous cannot be 
    // picked 
    int pick = hval[n] + maxLoot(hval, n - 2); 
    // if current element is not picked then previous 
    // element is picked 
    int notPick = maxLoot(hval, n - 1); 
  
    // return max of picked and not picked 
    return max(pick, notPick); 
} 
  
// Driver to test above code 
int main() 
{ 
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 }; 
    int n = sizeof(hval) / sizeof(hval[0]); 
    cout << "Maximum loot possible : "
         << maxLoot(hval, n - 1); 
    return 0; 
} 
  
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to find the maximum stolen value 
#include <stdio.h> 
  
// Find maximum between two numbers. 
int max(int num1, int num2) 
{ 
    return (num1 > num2) ? num1 : num2; 
} 
  
// calculate the maximum stolen value 
int maxLoot(int* hval, int n) 
{ 
    // base case 
    if (n < 0) 
        return 0; 
  
    if (n == 0) 
        return hval[0]; 
    // if current element is pick then previous cannot be 
    // picked 
    int pick = hval[n] + maxLoot(hval, n - 2); 
    // if current element is not picked then previous 
    // element is picked 
    int notPick = maxLoot(hval, n - 1); 
  
    // return max of picked and not picked 
    return max(pick, notPick); 
} 
  
// Driver to test above code 
int main() 
{ 
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 }; 
    int n = sizeof(hval) / sizeof(hval[0]); 
    printf("Maximum loot possible : %d ", 
           maxLoot(hval, n - 1)); 
    return 0; 
} 
  
// This code is contributed by Aditya Kumar (adityakumar129)

Java

/*package whatever //do not write package name here */
// Java program to find the maximum stolen value 
import java.io.*; 
  
class GFG  
{ 
    
  // Function to calculate the maximum stolen value 
  static int maxLoot(int hval[], int n) 
  { 
      
    // base case 
    if (n < 0) { 
      return 0; 
    } 
  
    if (n == 0) { 
      return hval[0]; 
    } 
      
    // if current element is pick then previous cannot 
    // be picked 
    int pick = hval[n] + maxLoot(hval, n - 2); 
      
    // if current element is not picked then previous 
    // element is picked 
    int notPick = maxLoot(hval, n - 1); 
  
    // return max of picked and not picked 
    return Math.max(pick, notPick); 
  } 
  
  // driver program 
  public static void main(String[] args) 
  { 
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 }; 
    int n = hval.length; 
    System.out.println("Maximum loot possible : "
                       + maxLoot(hval, n-1)); 
  } 
} 
  
// This code is contributed by sanskar84.

Python3

# Python3 program to find the maximum stolen value 
  
# calculate the maximum stolen value 
def maxLoot(hval,n): 
  
    # base case 
    if (n < 0): 
        return 0
  
    if (n == 0): 
        return hval[0] 
      
    # if current element is pick then previous cannot be 
    # picked 
    pick = hval[n] + maxLoot(hval, n - 2) 
    # if current element is not picked then previous 
    # element is picked 
    notPick = maxLoot(hval, n - 1) 
  
    # return max of picked and not picked 
    return max(pick, notPick) 
  
# Driver to test above code 
hval = [ 6, 7, 1, 3, 8, 2, 4 ] 
n = len(hval) 
print("Maximum loot possible : ",maxLoot(hval, n - 1)); 
  
# This code is contributed by shinjanpatra

C#

// C# program to find the maximum stolen value 
using System; 
  
public class GFG { 
  
    // Function to calculate the maximum stolen value 
    static int maxLoot(int[] hval, int n) 
    { 
  
        // base case 
        if (n < 0) { 
            return 0; 
        } 
  
        if (n == 0) { 
            return hval[0]; 
        } 
  
        // if current element is pick then previous cannot 
        // be picked 
        int pick = hval[n] + maxLoot(hval, n - 2); 
  
        // if current element is not picked then previous 
        // element is picked 
        int notPick = maxLoot(hval, n - 1); 
  
        // return max of picked and not picked 
        return Math.Max(pick, notPick); 
    } 
  
    static public void Main() 
    { 
  
        // Code 
        int[] hval = { 6, 7, 1, 3, 8, 2, 4 }; 
        int n = hval.Length; 
  
        Console.WriteLine("Maximum loot possible : "
                          + maxLoot(hval, n - 1)); 
    } 
} 
  
// This code is contributed by lokesmvs21.

Javascript

<script> 
  
// JavaScript program to find the maximum stolen value 
  
  
// calculate the maximum stolen value 
function maxLoot(hval,n) 
{ 
    // base case 
    if (n < 0) { 
        return 0; 
    } 
  
    if (n == 0) { 
        return hval[0]; 
    } 
    // if current element is pick then previous cannot be 
    // picked 
    let pick = hval[n] + maxLoot(hval, n - 2); 
    // if current element is not picked then previous 
    // element is picked 
    let notPick = maxLoot(hval, n - 1); 
  
    // return max of picked and not picked 
    return Math.max(pick, notPick); 
} 
  
// Driver to test above code 
  
let hval = [ 6, 7, 1, 3, 8, 2, 4 ]; 
let n = hval.length; 
document.write("Maximum loot possible : ",maxLoot(hval, n - 1)); 
  
  
// This code is contributed by shinjanpatra 
  
</script>

Output

Maximum loot possible : 19

Time Complexity: O(2^N). Every element has 2 choices to pick and not pick
Auxiliary Space: O(2^N). A recursion stack space is required of size 2ⁿ, so space complexity is O(2^N).

Tags:

#DSA #Dynamic Programming #Dynamic Programming

Find the maximum possible stolen value from houses using O(n) extra space

Find maximum possible stolen value from houses Dynamic Programming(Bottom Up Approach):

Find maximum possible stolen value from houses Dynamic Programming(Top-Down Approach)

C++

Java

Python3

C#

Javascript

Find maximum possible stolen value from houses (House Robber)

C++

C

Java

Python3

C#

Javascript

Similar Reads