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

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告