โปรแกรมค้นหาจำนวนการดำเนินการที่จำเป็นในการลด n เป็น 0 ใน C++

สมมติว่าเรามีตัวเลข n ทีนี้ลองพิจารณาการดำเนินการที่เราสามารถทำได้ 1. ลดค่า n ลงหนึ่ง 2. ถ้า n เป็นจำนวนคู่ ให้ลดค่าลงโดย n / 2 3. ถ้า n หารด้วย 3 ลงตัว ให้ลดลง 2 * (n / 3) ในที่สุดก็หา จำนวนการดำเนินการขั้นต่ำที่จำเป็นในการลด n เป็นศูนย์

ดังนั้น หากอินพุตเป็น n =16 ผลลัพธ์จะเป็น 5 เนื่องจาก n =16 แม้จะลดลง n/2 4 เท่า มันจะเป็น 1 จากนั้นลด 1 เพื่อให้ได้ 0 ดังนั้นรวม 5 การดำเนินงาน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดหนึ่งแผนที่ dp
กำหนดฟังก์ชัน dfs() ซึ่งจะใช้เวลา x
ถอยหลัง :=x
ถ้า x เป็น dp แล้ว −
- กลับ dp[x]
ถ้า x <=0 แล้ว −
- ผลตอบแทน x
ถ้า x เท่ากับ 1 แล้ว −
- กลับ 1
md2 :=x mod 2
md3 :=x mod 3
ret :=ขั้นต่ำของ {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);
}