C++でのHouseRobberII

あなたはプロの強盗だと考えてください。そして、あなたは通りに沿って家を奪うことを計画しています。各家には一定の金額が保管されています。すべての家は円形に配置されています。つまり、最初の家は最後の家の隣にあります。隣接する家屋にはセキュリティシステムが接続されており、同じ夜に隣接する2つの家屋が侵入された場合は自動的に警察に連絡することに注意する必要があります。したがって、各家の金額を表す整数のリストがある場合は、警察に警告せずに1晩に奪うことができる最大金額を決定します。したがって、配列が[1,2,3,1]の場合、出力は4になります。

これを解決するには、次の手順に従います-

• 私たちはsolve（）と呼ばれる1つのモジュールを使用しています。このモジュールは、配列を取得し、開始と終了を行い、以下のように動作します-
• ans：=nums [start]
• 動的計画法用に1つのテーブルを作成します。その名前はdpで、サイズはnumsサイズと同じです。
• dp [start]：=nums [start]
• for i：=start + 1 to end
  • 最後：=dp [i – 1]
  • lastToLast：=0（i – 2の場合）、それ以外の場合はdp [i – 2]
  • dp [i]：=最大nums [i]+lastToLastおよびlast
  • ans：=dp[i]とansの最大値
• 回答を返す
• 強盗は以下のように行われます-
• n：=numsのサイズ
• nがゼロの場合、0を返します
• n =1の場合、nums[0]を返します
• solve（nums、0、n-2）、solve（nums、1、n – 1）の最大値を返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector <int>& nums, int start, int end){
      int ans = nums[start];
      vector <int> dp(nums.size());
      dp[start] = nums[start];
      for(int i = start + 1; i <= end; i++){
         int last = dp[i - 1];
         int lastToLast = i - 2 < start? 0 : dp[i - 2];
         dp[i] = max(nums[i] + lastToLast, last);
         ans = max(dp[i], ans);
      }
      return ans;
   }
   int rob(vector<int>& nums) {
      int n = nums.size();
      if(!n)return 0;
      if(n == 1)return nums[0];
      return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
   }
};
main(){
   vector<int> v = {1,2,3,5};
   Solution ob;
   cout << ob.rob(v);
}

入力

[1,2,3,5]

出力

7