程序查找在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操作。

示例

让我们看下面的实现以更好地理解-

#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