C++でnを0に減らすために必要な操作の数を見つけるプログラム

数nがあるとします。ここで、1。nを1つデクリメントする2. nが偶数の場合は、n / 2をデクリメントします。3。nが3で割り切れる場合は、2 *（n / 3）をデクリメントします。 nをゼロにデクリメントするために必要な操作の最小数。

したがって、入力がn =16の場合、出力は5になります。これは、n=16でもn/2を4倍減らすと、1になります。次に1を減らすと、0になります。合計5操作。

これを解決するには、次の手順に従います-

• 1つのマップdpを定義する

• 関数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);
}

入力

16

出力

5