Số phép toán ít nhất để biểu diễn số trong C++

Cho số nguyên dương x, viết biểu thức dạng x op1 x op2 x ... (phép toán +, -, *, /) sao cho giá trị bằng target, dùng ít phép toán nhất. Quy tắc: phép chia trả về số hữu tỷ, không ngoặc, ưu tiên * / trước + -, không cho phép toán tử một ngôi.

Ví dụ: x=4, target=15 → 3 phép toán (4*4 - 4/4).

Giải thuật

1. Nếu target == x: trả về 0.
2. Nếu x > target: trả về min((x-target)*2, target*2-1) (chỉ dùng + và -).
3. Tìm lũy thừa sum = x^t ≥ target (t là số phép *).
4. Nếu sum == target: trả về t.
5. Đệ quy: l = leastOps(x, target - sum/x) + t - 1 (dùng sum/x làm cơ sở, cộng thêm). r = leastOps(x, sum - target) + t (dùng sum làm cơ sở, trừ đi).
6. Trả về 1 + min(l, r).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        if(target == x) return 0;
        if(x > target) return min((x - target) * 2, (target * 2) - 1);
        lli sum = x;
        int t = 0;
        while(sum < target){ sum *= x; t++; }
        if(sum == target) return t;
        int l = INT_MAX, r = INT_MAX;
        if(sum - target < target) r = leastOpsExpressTarget(x, sum - target) + t;
        l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
        return min(l, r) + 1;
    }
};
int main(){
    Solution ob;
    cout << (ob.leastOpsExpressTarget(4, 15));
}

Đầu vào

4, 15

Đầu ra

3