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 ऑपरेशन्स।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

एक मैप dp परिभाषित करें
एक फंक्शन dfs() परिभाषित करें जो x लेता है
ret := x
यदि x, dp में है, तो dp[x] वापस करें
यदि x ≤ 0, तो x वापस करें
यदि x == 1, तो 1 वापस करें
md2 := x mod 2
md3 := x mod 3
ret := min({ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3)})
dp[x] = ret वापस करें
मुख्य विधि से 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);
}