ধরুন আমাদের কাছে শিলার একটি সংগ্রহ রয়েছে, এখন প্রতিটি শিলার একটি ধনাত্মক পূর্ণসংখ্যা ওজন রয়েছে। প্রতিটি পালা, আমরা যে কোনো দুটি শিলা চয়ন এবং তাদের একসঙ্গে চূর্ণ. যদি পাথরের ওজন x এবং y এর সাথে x <=y থাকে। এই স্ম্যাশের ফলাফল হবে −
-
x =y হলে, উভয় পাথরই সম্পূর্ণরূপে ধ্বংস হয়ে যায়;
-
যদি x !=y হয়, x এর ওজনের পাথরটি সম্পূর্ণরূপে ধ্বংস হয়ে গেছে এবং y ওজনের পাথরের নতুন ওজন y-x আছে।
অবশেষে, সর্বাধিক 1টি পাথর বাকি আছে। আমাদের এই পাথরের সম্ভাব্য ক্ষুদ্রতম ওজন খুঁজে বের করতে হবে (কোনও পাথর না থাকলে ওজন 0 হয়।)
সুতরাং উদাহরণস্বরূপ, যদি ইনপুটটি [2,7,4,1,8,1] এর মত হয়, তাহলে আউটপুট হবে 1। এর কারণ হল যদি আমরা স্ম্যাশ (2,4), তাহলে নতুন অ্যারে হবে [2] ,7,1,8,1], তারা smash (7,8), নতুন অ্যারে হবে [2,1,1,1], তারপর smash (2,1), অ্যারে হবে [1,1, 1], সেই স্ম্যাশের পরে (1,1), তাই শুধুমাত্র 1 থাকবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=পাথরের অ্যারের আকার, মোট সেট করুন :=0
-
0 থেকে n – 1
রেঞ্জের i জন্য-
মোট :=মোট + পাথর[i]
-
-
req :=মোট / 2
-
req + 1 আকারের একটি অ্যারে ডিপি তৈরি করুন এবং এটিকে মিথ্যা মান দিয়ে পূরণ করুন
-
dp[0] :=সত্য, পৌঁছান :=0
-
0 থেকে n – 1
রেঞ্জের i জন্য-
j এর জন্য :=req, যখন j – স্টোন[i]>=0, j কমিয়ে 1
-
dp[j] :=মিথ্যা যখন (dp[j] এবং dp[j – পাথর[i]]) উভয়ই মিথ্যা, অন্যথায় সত্য
-
যদি dp[j] সত্য হয়, তাহলে পৌঁছান :=পৌঁছানোর সর্বোচ্চ এবং j
-
-
-
মোট রিটার্ন - (2 * পৌঁছানো)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
