C++ में n से 0 तक कम करने के लिए आवश्यक संक्रियाओं की संख्या ज्ञात करने का कार्यक्रम

मान लीजिए कि हमारे पास एक संख्या 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