Chương trình tìm số phép toán giảm n về 0 tối thiểu trong C++

Mô tả bài toán

Cho số n. Mỗi phép toán có thể: 1) giảm 1; 2) nếu chẵn giảm n/2; 3) nếu chia hết 3 giảm 2*(n/3). Tìm số phép tối thiểu để n về 0.

Ví dụ: n=16 → 5 (16→8→4→2→1→0).

Giải thuật (Đệ quy có nhớ)

1. dp[x] = số phép tối thiểu từ x về 0.
2. dfs(x):
   • Nếu x ≤ 0: return 0.
   • Nếu x == 1: return 1.
   • md2 = x%2, md3 = x%3.
   • ret = min(x, md2+1+dfs((x-md2)/2), md3+1+dfs((x-md3)/3)).
   • Lưu dp[x] = ret.

Ví dụ minh họa (C++)

#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);
    return 0;
}

Đầu vào

16

Đầu ra

5