मान लीजिए कि हमारे पास एक संख्या n है। अब एक ऑपरेशन पर विचार करें जहां हम या तो 1. घटा सकते हैं n एक से 2. यदि n सम संख्या है, तो इसे n / 2 3 से घटाएं। यदि n 3 से विभाज्य है, तो 2 * (n / 3) से कमी अंत में खोजें n से शून्य तक कम करने के लिए आवश्यक संचालन की न्यूनतम संख्या।
इसलिए, यदि इनपुट n =16 की तरह है, तो आउटपुट 5 होगा, क्योंकि n =16 फिर भी इसे n/2 4 गुना घटाता है, यह 1 होगा। फिर इसे 1 से घटाकर 0 प्राप्त करें। तो कुल 5 संचालन।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक मानचित्र डीपी परिभाषित करें
-
फ़ंक्शन को परिभाषित करें dfs(), इसमें x लगेगा,
-
रिट :=x
-
यदि x dp में है, तो -
-
वापसी डीपी [एक्स]
-
-
यदि x <=0, तो -
-
वापसी x
-
-
यदि x 1 के समान है, तो -
-
वापसी 1
-
-
एमडी2:=एक्स मॉड 2
-
एमडी3:=एक्स मॉड 3
-
ret :=न्यूनतम {ret, md2 + 1 + dfs ((x - md2) / 2), md3 + 1 + dfs ((x - md3) / 3)}
-
वापसी डीपी [एक्स] =सेवानिवृत्त
-
मुख्य विधि से कॉल करें और dfs(n)
. लौटाएं
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
unordered_map <int, int> dp;
int dfs(int x){
int ret = x;
if(dp.count(x))
return dp[x];
if(x <= 0)
return x;
if(x == 1)
return 1;
int md2 = x % 2;
int md3 = x % 3;
ret = min({ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3)});
return dp[x] = ret;
}
int solve(int n) {
return dfs(n);
}
int main(){
int n = 16;
cout << solve(n);
} इनपुट
16
आउटपुट
5
