数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究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
更新于：2020-12-22
浏览量：159
广告