資料結構
網路
關係資料庫管理系統 (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
廣告