強盜屋


難度級別
經常問 亞馬遜 蘋果 思科 Expedia的 谷歌 Microsoft微軟 神諭
深度優先搜索

房屋強盜問題 指出,在一個城市的鄰里,只有一排n座房屋。 一個小偷正計劃在這附近進行搶劫。 他知道每個房子裡藏了多少金。

但是,為了避免引發警報並引起懷疑,他計劃進行搶劫,以免洗劫連續兩棟房屋。 即如果索引處的房子= i 被搶劫了,房屋在 i-1的 我+1 沒有被洗劫。

找出小偷在給定的限制下可以偷走的最大黃金數量。

Input 1: arr[] = [2,3,4,2,3]
         Maximum gold = [2, X, 4, X, 3] = 9
Output: 6


Input 2: arr[] = [3,8,10,4,2,3]
         Maximum gold = [3, X, 10, X, X, 3] = 16
Output: 15


Input 2: arr[] = [3,8,10,4,2,3,11] 
         Maximum gold = [3, X, 10, X, 2, X, 11] = 26 
Output: 26

解釋:在示例2中,在給定約束的情況下,小偷必須到達第一,第三和第六宮以收集最大數量的黃金。

解決方案類型

  1. 遞歸
  2. 動態編程 :
    • 記憶解決方案
    • 列表解決方案
    • 空間優化的DP解決方案

House Robber的遞歸解決方案

給定一個 排列,解決方案是在沒有兩個選定元素相鄰的地方找到最大和子序列。 我們通過以下方式實現此目的:

  1. 開始從右向左遍歷arr []。
  2. 如果選擇了一個元素arr [i],則不能選擇下一個元素(arr [i-1])。
  3. 如果未選擇元素(arr [i]),則可以選擇下一個元素arr [i-1]。
  4. 遞歸執行步驟2和3,並返回在步驟2和3中獲得的最大值。

C ++程序

#include <iostream>
using namespace std;

int maxGold (int gold[],int n)
{
    if(n <= 0)
    return 0;
    
    // select the current element
    int select = gold[n-1] + maxGold(gold,n-2);
    // not selecting the current element
    int notselect = maxGold(gold,n-1);
    
    // return maximum of both of above
    return max(select,notselect);
}

int main() 
{
  int gold[] = {3,8,10,4,2,3};
  int n = sizeof(gold)/sizeof(int);
  
  cout<<"Maximum gold looted = "<<maxGold(gold,n);
  return 0;
}
Maximum gold looted = 16

Java程序

import java.io.*;

class tutorialcup
{
    static int maxGold (int gold[],int n)
    {
        if(n <= 0)
        return 0;
        
        // select the current element
        int select = gold[n-1] + maxGold(gold,n-2);
        // not selecting the current element
        int notselect = maxGold(gold,n-1);
        
        // return maximum of both of above
        return Math.max(select,notselect);
    }
    
  public static void main (String[] args) 
  {
    int gold[] = {3,8,10,4,2,3};
    	        int n = gold.length;
    	
    	        System.out.print("Maximum gold looted = "+maxGold(gold,n));
  }
}
Maximum gold looted = 16

複雜度分析

  1. 時間複雜度T(n)= O(2n),遞歸調用。
  2. 空間複雜度A(n)= O(1)

動態編程

遞歸解決方案的主要缺點是其指數時間複雜度。 當遞歸解決方案嘗試反复解決某些子問題時,就會發生這種情況。 這會增加 算法。 遞歸解的指數時間複雜度可以使用以下方法降低為線性時間複雜度 動態編程。 此方法利用額外的空間來存儲子問題的解決方案,在程序的後面,如果再次調用該子問題,則可以直接使用其存儲的值,而不用重新計算它。 這將復雜度從指數級降​​低到線性級。

我們將執行 動態編程 解決方法如下:

房屋搶劫者的記憶解決方案

在這裡我們創建一張地圖 備忘錄 並將子問題作為鍵存儲,並將子問題的解決方案存儲為地圖的值。 實施代碼類似於遞歸方法,只是對Map進行了細微的更改和使用。

備忘錄映射如下:

強盜屋

C ++程序

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maxGold (int gold[],int n, unordered_map <int,int> &memo)
{
    int key = n;
    
    // if solution for subproblem maxGold(gold,n,memo)
    // has not been calculated
    // calulate it
    if(memo.find(key) == memo.end())
    {
        if(n <= 0)
        {
            memo[key] = 0;
            return memo[key];
        }
        
        // select the current element
        int select = gold[n-1] + maxGold(gold,n-2,memo);
        // not selecting the current element
        int notselect = maxGold(gold,n-1,memo);
        
        // return maximum of both of above
        memo[key] = max(select,notselect);
    }
    
    // return value of subproblem after being calculated
    // or if already present
    return memo[key];
}

// main function to implement above function
int main() 
{
  int gold[] = {3,8,10,4,2,3};
  int n = sizeof(gold)/sizeof(int);
  
  // map to store mapping between particular subproblem and it's value
  unordered_map <int,int> memo;
  cout<<"Maximum gold looted = "<<maxGold(gold,n,memo);
  return 0;
}
Maximum gold looted = 16

Java程序

import java.io.*;
import java.util.*;
class tutorialcup
{
    static int maxGold (int gold[],int n, HashMap <Integer,Integer> memo)
    {
        int key = n;
        
        // if solution for subproblem maxGold(gold,n,memo)
        // has not been calculated
        // calulate it
        if(!memo.containsKey(key))
        {
            if(n <= 0)
            {
                memo.put(key,0);
                return memo.get(key);
            }
            
            // select the current element
            int select = gold[n-1] + maxGold(gold,n-2,memo);
            // not selecting the current element
            int notselect = maxGold(gold,n-1,memo);
            
            // return maximum of both of above
            memo.put(key, Math.max(select,notselect));
        }
        
        // return value of subproblem after being calculated
        // or if already present
        return memo.get(key);
    }

    
  public static void main (String[] args) 
  {
    int gold[] = {3,8,10,4,2,3};
    	int n = gold.length;
    	
    	HashMap <Integer,Integer> memo = new HashMap <Integer,Integer>();
    	System.out.print("Maximum gold looted = "+maxGold(gold,n,memo));
  }
}
Maximum gold looted = 16

複雜度分析

  1. 時間複雜度:T(n)= O(n),單數組遍歷。
  2. 空間複雜度:A(n)= O(n),地圖的額外空間。

房屋強盜列表解決方案

我們創建一個 (線性數組),其中子問題是數組索引,子問題的解決方案是該特定索引處的值。

算法

    1. 創建一個數組 桌子[] 存儲子問題
    2. 定義一些基本情況(對於n = 0,1,2)。
    3. n = 0時返回0。
    4. 提交 桌子[0] = 金[0]桌子[1] =最大(金[0], 金子[1])。
    5. 從i = 2遍歷數組到數組末尾。
    6. 對於每個索引,更新表[I]的 =最大(表[i-2] +黃金[i] , 桌子[i-1]),此步驟定義了兩種情況,如果選擇了一個元素,則無法選擇前一個元素;如果未選擇一個元素,則可以選擇前一個元素。
    7. 返回值表[n-1]。

我們在下面顯示上述過程:

強盜屋

C ++程序

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maxGold (int gold[],int n1)
{
    // base cases
    if (n1 == 0) 
        return 0; 
    if (n1 == 1) 
        return gold[0]; 
    if (n1 == 2) 
        return max(gold[0], gold[1]); 
  
    // table[i] represent the maximum value stolen 
    // so far after reaching house i. 
    int table[n1]; 
  
    // Initialize the table[0] and table[1] 
    table[0] = gold[0]; 
    table[1] = max(gold[0], gold[1]); 
  
    // Fill remaining positions 
    for (int i = 2; i<n1; i++) 
        table[i] = max(gold[i]+table[i-2], table[i-1]); 
  
    return table[n1-1]; 
}

// main function to implement above function
int main() 
{
  int gold[] = {3,8,10,4,2,3};
  int n = sizeof(gold)/sizeof(int);
  
  cout<<"Maximum gold looted = "<<maxGold(gold,n);
  return 0;
}
Maximum gold looted = 16

Java程序

import java.io.*;
import java.util.*;
class tutorialcup
{
    static int maxGold (int gold[],int n)
    {
        // base cases
        if (n == 0) 
            return 0; 
        if (n == 1) 
            return gold[0]; 
        if (n == 2) 
            return Math.max(gold[0], gold[1]); 
      
        // table[i] represent the maximum value stolen 
        // so far after reaching house i. 
        int table[] = new int[n]; 
      
        // Initialize the table[0] and table[1] 
        table[0] = gold[0]; 
        table[1] = Math.max(gold[0], gold[1]); 
      
        // Fill remaining positions 
        for (int i = 2; i<n; i++) 
            table[i] = Math.max(gold[i]+table[i-2], table[i-1]); 
      
        return table[n-1]; 
    }
    
  public static void main (String[] args) 
  {
    int gold[] = {3,8,10,4,2,3};
    	int n = gold.length;
    	
    	System.out.print("Maximum gold looted = "+maxGold(gold,n));
  }
}
Maximum gold looted = 16

複雜度分析

  1. 時間複雜度:T(n)= O(n),單次遍歷。
  2. 對於表[],空間複雜度:A(n)= O(n)。

空間優化的DP解決方案,適用於強盜

通過仔細觀察表格化的DP解,我們推論只需要最後兩個索引(i-1和i-2)來計算第i個子問題的解。 即我們只需要table [i-2]和table [i-1]來計算table [i]的值。 因此,我們消除了table []數組,並將其替換為兩個輔助變量。

算法

  1. 定義一些基本情況(對於n = 0,1,2)。
  2. n = 0時返回0。
  3. 創建兩個變量 val1val2。
  4. 分配 val1 =黃金[0] , value2 =最大(金[0][1])。
  5. 確定 一個變量 最大戰利品 存儲答案。
  6. 從第二個元素到數組末尾遍歷數組。
  7. 對於每個索引= i,更新 最大戰利品  =最大(val1 +金[i],val2),此步驟定義了兩種情況,如果選擇了一個元素,則無法選擇前一個元素;如果未選擇一個元素,則可以選擇前一個元素。
  8. 另外,對於每個索引,更新 val1 = val2val2 = maxLoot。
  9. 返回的最終值 maxLoot, 數組遍歷後。

C ++程序

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maxGold (int gold[],int n)
{
    // base cases
    if (n == 0) 
        return 0; 
    if (n == 1) 
        return gold[0]; 
    if (n == 2) 
        return max(gold[0], gold[1]); 
  
    // define and initialize val1 and val2
    int val1 = gold[0]; 
    int val2 = max(gold[0], gold[1]); 
    // define maxLoot to obtain maximum value of gold stolen
    int maxLoot;
    
    // traverse to find the final value of maxLoot
    for (int i = 2; i<n; i++) 
    {
        maxLoot = max(gold[i]+val1, val2); 
        val1 = val2;
        val2 = maxLoot;
    }
  
    return maxLoot; 
}

// main function to implement above function
int main() 
{
  int gold[] = {3,8,10,4,2,3};
  int n = sizeof(gold)/sizeof(int);
  
  cout<<"Maximum gold looted = "<<maxGold(gold,n);
  return 0;
}
Maximum gold looted = 16

Java程序

import java.io.*;
import java.util.*;
class tutorialcup
{
    static int maxGold (int gold[],int n)
    {
        // base cases
        if (n == 0) 
            return 0; 
        if (n == 1) 
            return gold[0]; 
        if (n == 2) 
            return Math.max(gold[0], gold[1]);
      
        // define and initialize val1 and val2
        int val1 = gold[0]; 
        int val2 = Math.max(gold[0], gold[1]); 
        int maxLoot = 0;
        
        // traverse to find the final value of maxLoot
        for (int i = 2; i<n; i++) 
        {
            maxLoot = Math.max(gold[i]+val1, val2);
            val1 = val2;
            val2 = maxLoot;
        }
      
        return maxLoot; 
    }
    
  public static void main (String[] args) 
  {
    int gold[] = {3,8,10,4,2,3};
    	int n = gold.length;
    	
    	System.out.print("Maximum gold looted = "+maxGold(gold,n));
  }
}
Maximum gold looted = 16

複雜度分析

  1. 時間複雜度:T(n)= O(n),單次遍歷。
  2. 空間複雜度:A(n)= O(1),僅使用兩個額外變量。

參考