C++-এ হাউস রোবার II (House Robber II - Circular Houses)

আপনি একজন পেশাদার চোর। একটি স্ট্রিটের বাড়িগুলো বৃত্তাকার (circular) আকারে সাজানো আছে, অর্থাৎ প্রথম বাড়ি এবং শেষ বাড়ি প্রতিবেশি। প্রতিটি বাড়িতে কিছু টাকা আছে। দুটি প্রতিবেশি বাড়ি একসাথে চুরি করলে পুলিশ এলার্ত পাবে। এক রাতে সর্বোচ্চ কত টাকা চুরি করা যায় তা বের করুন।

উদাহরণ

ইনপুট: [1,2,3,1] → আউটপুট: ৪

সমাধান

যেহেতু বাড়িগুলো বৃত্তাকার, তাই দুটি কেস বিবেচনা করুন:

1. প্রথম বাড়ি চুরি করলে শেষ বাড়ি চুরি করা যাবে না → solve(0, n-2)
2. শেষ বাড়ি চুরি করলে প্রথম বাড়ি চুরি করা যাবে না → solve(1, n-1)

প্রতিটি কেসে সাধারণ হাউস রোবার DP লাগিয়ে সর্বোচ্চ মান বের করুন।

C++ প্রোগ্রাম উদাহরণ

#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));
    }
};

int main() {
    vector<int> v = {1, 2, 3, 5};
    Solution ob;
    cout << ob.rob(v);
    return 0;
}

ইনপুট / আউটপুট

Input: [1,2,3,5]
Output: 7