C++ এ n 0 থেকে কমাতে প্রয়োজনীয় অপারেশনের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা n আছে। এখন একটি ক্রিয়াকলাপ বিবেচনা করুন যেখানে আমরা হয় 1 করতে পারি। n একটি 2 দ্বারা হ্রাস। যদি n জোড় সংখ্যা হয়, তবে এটি n / 2 দ্বারা হ্রাস করুন 3। n যদি 3 দ্বারা বিভাজ্য হয়, তবে 2 * (n / 3) দ্বারা হ্রাস করুন অবশেষে খুঁজে বের করুন এন-কে শূন্যে কমাতে প্রয়োজনীয় ন্যূনতম সংখ্যা।

সুতরাং, যদি ইনপুটটি n =16 এর মত হয়, তাহলে আউটপুট হবে 5, যেমন n =16 তারপরও এটি n/2 কমিয়ে 4 বার, এটি 1 হবে। তারপর 0 পেতে এটি 1 কমিয়ে দিন। সুতরাং মোট 5 অপারেশন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি মানচিত্র ডিপি
সংজ্ঞায়িত করুন
একটি ফাংশন সংজ্ঞায়িত করুন dfs(), এটি x,
লাগবে
ret :=x
যদি x dp-এ থাকে, তাহলে −
- dp[x]
  ফেরত দিন
যদি x <=0, তাহলে −
- রিটার্ন x
যদি x 1 এর মত হয়, তাহলে −
- রিটার্ন 1
md2 :=x mod 2
md3 :=x mod 3
ret :=সর্বনিম্ন {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);
}