โปรแกรมหาจำนวนขั้นตอนน้อยสุดลด n เป็น 0 ใน C++

ให้ตัวเลข n ดำเนินการได้ 3 แบบ: 1) ลด 1, 2) ถ้าเลขคู่ ลด n/2, 3) ถ้าหาร 3 ลงตัว ลด 2×(n/3) หาขั้นตอนน้อยสุดถึง 0

ตัวอย่าง: n=16 → 5 ขั้นตอน (16→8→4→2→1→0)

ขั้นตอนการแก้ปัญหา (DP + Memoization)

1. dp[x] = คำตอบสำหรับ x
2. dfs(x):
   • ถ้า x <= 0: คืน x
   • ถ้า x == 1: คืน 1
   • md2 = x%2, md3 = x%3
   • ret = min(x, md2+1+dfs((x-md2)/2), md3+1+dfs((x-md3)/3))
   • เก็บและคืน dp[x]

เหตุผล: ลด md2 ครั้งเพื่อให้หาร 2 ลงตัว แล้วค่อยหาร 2 (1 ขั้นตอน) เช่นเดียวกันหาร 3

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

unordered_map<int,int> dp;

int dfs(int x) {
    if (dp.count(x)) return dp[x];
    if (x <= 0) return x;
    if (x == 1) return 1;
    int md2 = x % 2, md3 = x % 3;
    int ret = min({x, 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() {
    cout << solve(16); // 5
    return 0;
}

อินพุต

16

เอาต์พุต

5