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后，将变为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);
}

输入

16

输出

5

Arnab Chakraborty

更新于：2020-12-22

浏览量：159

开启您的职业生涯

完成课程获得认证

开始学习