程序查找在C ++中将n减少为0所需的操作数
假设我们有一个数字n。现在考虑一个操作，其中我们可以1.将n减1。2.如果n为偶数，则将其减n/2。3.如果n被3整除，则将其减2*（n/3）最后找到将n减为零所需的最小操作数。
因此，如果输入像n=16，则输出将为5，因为n=16甚至将其减小n/24次，将为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