# 強盜屋

## 例

```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```

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）

## 動態編程

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

#### 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
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
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解決方案，適用於強盜

#### 算法

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），僅使用兩個額外變量。