মান लीজিয়ে আমাদের পাথরের একটি সংগ্রহ আছে, যেখানে প্রতিটি পাথরের একটি ধনাত্মক পূর্ণসংখ্যা ওজন আছে। প্রতিটি চুলে, আমরা যেকোনো দুটি পাথর বেছে নিয়ে সেগুলোকে একসাথে ধাক্কা দিই। যদি পাথর দুটির ওজন x এবং y হয় যেখানে x ≤ y। এই ধাক্কার ফলাফল হবে -
যদি x = y হয়, তবে দুটি পাথরই সম্পূর্ণ ধ্বংস হয়ে যায়;
যদি x != y হয়, তবে ওজন x-এর পাথরটি সম্পূর্ণ ধ্বংস হয়ে যায়, এবং ওজন y-এর পাথরটির নতুন ওজন হয় y-x।
শেষে, højতrophes ১টি পাথর থাকতে পারে। আমাদের এই পাথরের সম্ভাব্য সর্বনিম্ন ওজন খুঁজে বের করতে হবে (যদি কোনো পাথর না থাকে তবে ওজন ০)।
উদাহরণস্বরূপ, যদি ইনপুট হয় [2,7,4,1,8,1], তবে আউটপুট হবে ১। কারণ যদি আমরা (2,4) ধাক্কা দিই, তবে নতুন অ্যারে হবে [2,7,1,8,1], তারপর (7,8) ধাক্কা দিলে অ্যারে হবে [2,1,1,1], এরপর (2,1) ধাক্কা দিলে অ্যারে হবে [1,1,1], এরপর (1,1) ধাক্কা দিলে শুধু ১ বাঁচে থাকবে।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
n := stones অ্যারের আকার, total := 0 সেট করুন
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
total := total + stones[i]
req := total / 2
req + 1 আকারের একটি dp অ্যারে তৈরি করুন এবং false দিয়ে পূরণ করুন
dp[0] := true, reach := 0
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
j = req থেকে j - stones[i] >= 0 পর্যন্ত j-- করে লুপ চালান
dp[j] := false যদি (dp[j] এবং dp[j - stones[i]]) উভয়ই false হয়, অন্যথায় true
যদি dp[j] true হয়, তবে reach := max(reach, j)
return total - (2 * reach)
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int lastStoneWeightII(vector<int>& stones) { int n = stones.size(); int total = 0; for(int i = 0; i < n; i++){ total += stones[i]; } int req = total / 2; vector <bool> dp(req + 1, false); dp[0] = true; int reach = 0; for(int i = 0; i < n; i++){ for(int j = req; j - stones[i] >= 0; j--){ dp[j] = dp[j] || dp[j - stones[i]]; if(dp[j]) reach = max(reach, j); } } return total - (2 * reach); } }; main(){ vector<int> v = {2,7,4,1,8,1}; Solution ob; cout << (ob.lastStoneWeightII(v)); }ইনপুট
[2,7,4,1,8,1]
আউটপুট
1
