मान लीजिए कि हमारे पास चट्टानों का एक संग्रह है, अब प्रत्येक चट्टान का एक धनात्मक पूर्णांक भार है। प्रत्येक मोड़ में, हम किन्हीं दो चट्टानों को चुनते हैं और उन्हें एक साथ तोड़ते हैं। यदि पत्थरों का भार x और y है और x <=y है। इस स्मैश का परिणाम होगा -
-
यदि x =y, तो दोनों पत्थर पूरी तरह नष्ट हो जाते हैं;
-
अगर x !=y, तो वजन x का पत्थर पूरी तरह से नष्ट हो गया है, और वजन y के पत्थर का नया वजन y-x है।
अंत में, ज़्यादा से ज़्यादा 1 पत्थर बचा है। हमें इस पत्थर का सबसे छोटा संभव वजन ज्ञात करना है (यदि कोई पत्थर नहीं बचा है तो वजन 0 है।)
तो उदाहरण के लिए, यदि इनपुट [2,7,4,1,8,1] जैसा है, तो आउटपुट 1 होगा। ,7,1,8,1], वे स्मैश करते हैं (7,8), नया ऐरे [2,1,1,1] होगा, फिर स्मैश (2,1), ऐरे [1,1,] होगा 1], उस स्मैश के बाद (1,1), तो केवल 1 ही होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n:=स्टोन्स ऐरे का आकार, कुल सेट करें:=0
-
मेरे लिए 0 से n - 1 की सीमा में
-
कुल:=कुल + पत्थर[i]
-
-
अनुरोध :=कुल/2
-
req + 1 आकार की एक सरणी dp बनाएं और इसे झूठे मानों से भरें
-
डीपी [0] :=सच, पहुंच :=0
-
मेरे लिए 0 से n - 1 की सीमा में
-
j के लिए :=req, जब j - स्टोन्स[i]>=0, j को 1 से घटाएं
-
डीपी [जे]:=झूठा जब (डीपी [जे] और डीपी [जे - पत्थर [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