Hiểu bài toán

Bài toán yêu cầu tìm số bước ít nhất để biến đổi một số nguyên dương n về 1 thông qua ba phép toán: trừ 1, chia cho 2 (nếu chia hết), hoặc chia cho 3 (nếu chia hết). Mỗi phép toán được tính là một bước. Đây là bài toán tìm đường đi ngắn nhất trên đồ thị các số nguyên dương, với các cạnh nối giữa n và các số có thể đến được (n-1, n/2, n/3).

Các cách tiếp cận

Cách Quy hoạch động

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t, n;
    cin >> t;

    int maxN = 100000 + 5;
    vector<int> dp(maxN, maxN);
    dp[1] = 0;

    for (int i = 2; i < maxN; i++) {
        dp[i] = dp[i-1] + 1;
        if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i/2] + 1);
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i/3] + 1);
        }
    }

    for (int i = 0; i < t; i++) {
        cin >> n;
        cout << dp[n] << "\n";
    }

    return 0;
}

• Time Complexity: O(N) với N là giá trị lớn nhất của n (khoảng 10^5)
• Space Complexity: O(N) để lưu mảng dp

Sử dụng quy hoạch động để tính trước số bước tối thiểu cho tất cả các số từ 1 đến giới hạn lớn nhất. Với mỗi số i, ta tính dp[i] dựa trên các số trước đó: dp[i] = min(dp[i-1] + 1, dp[i/2] + 1 nếu i chia hết cho 2, dp[i/3] + 1 nếu i chia hết cho 3). Sau đó chỉ cần tra cứu mảng dp cho mỗi test case.

Cách Quy hoạch động với đệ quy có nhớ (Memoization)

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

map<int,int> mem;
int cal(int n){
    if(n==1) return 0;
    if(mem.find(n-1)==mem.end()) mem[n-1] = cal(n-1);
    if(n%2==0&&mem.find(n/2)==mem.end()) mem[n/2] = cal(n/2);
    if(n%3==0&&mem.find(n/3)==mem.end()) mem[n/3] = cal(n/3);
    if(n%6==0){
        return min({mem[n-1],mem[n/2],mem[n/3]})+1;
    }
    else if(n%2==0&&n%3!=0){
        return min(mem[n-1],mem[n/2])+1;
    }
    else if(n%2!=0&&n%3==0){
        return min(mem[n-1],mem[n/3])+1;
    } 
    else return mem[n-1]+1;
}

int main(){
    int tc,n;
    cin>>tc;
    while(tc--){
        int res=0;
        cin>>n;
        cout<<cal(n)<<"\n";
    }
}

• Time Complexity: O(N log N) trong trường hợp xấu nhất
• Space Complexity: O(N) để lưu trữ các kết quả đã tính

Sử dụng đệ quy quay lui với cơ chế ghi nhớ (memoization) để tránh tính toán lại các giá trị đã gặp. Hàm cal(n) trả về số bước tối thiểu từ n về 1. Với mỗi n, ta đệ quy tính toán các giá trị của n-1, n/2 (nếu chia hết), n/3 (nếu chia hết) và lưu vào map để sử dụng lại. Tuy nhiên, cách này có thể gây tràn stack với n lớn và hiệu năng không tốt bằng quy hoạch động tuần tự.

Cách BFS (Tìm đường đi ngắn nhất)

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

int solve(int n) {
    if (n == 1) return 0;
    queue<pair<int, int>> q;
    q.push({n, 0});
    unordered_set<int> visited;
    visited.insert(n);

    while (!q.empty()) {
        auto [curr, steps] = q.front();
        q.pop();

        if (curr == 1) return steps;

        // Thử các phép biến đổi
        if (curr - 1 >= 1 && visited.find(curr - 1) == visited.end()) {
            visited.insert(curr - 1);
            q.push({curr - 1, steps + 1});
        }
        if (curr % 2 == 0 && visited.find(curr / 2) == visited.end()) {
            visited.insert(curr / 2);
            q.push({curr / 2, steps + 1});
        }
        if (curr % 3 == 0 && visited.find(curr / 3) == visited.end()) {
            visited.insert(curr / 3);
            q.push({curr / 3, steps + 1});
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        cout << solve(n) << "\n";
    }
    return 0;
}

• Time Complexity: O(N) trong trường hợp xấu nhất
• Space Complexity: O(N) để lưu các nút đã thăm

Giải quyết bài toán như một bài toán tìm đường đi ngắn nhất trên đồ thị. Bắt đầu từ n, ta dùng BFS để duyệt qua các nút kề (các số có thể đến được bằng một phép biến đổi). Khi gặp 1, số bước đã đi qua chính là đáp án. BFS đảm bảo tìm được đường đi ngắn nhất.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có cấu trúc quy hoạch động tự nhiên: số bước từ n về 1 phụ thuộc vào số bước từ các số nhỏ hơn (n-1, n/2, n/3) về 1.
• Quy hoạch động tuần tự từ 1 đến N là hiệu quả nhất cho các test case có n ≤ 10^5 vì tính được trước tất cả các giá trị và tra cứu ngay.
• Nếu số test case ít nhưng n lớn, có thể dùng đệ quy có nhớ hoặc BFS để không phải tính toán thừa cho các giá trị không cần thiết.

Lỗi thường gặp

• Quên kiểm tra điều kiện chia hết trước khi thực hiện phép chia, dẫn đến lỗi logic hoặc truy cập ngoài vùng nhớ.
• Sử dụng đệ quy không có cơ chế ghi nhớ có thể gây trùng lặp tính toán và tràn stack với n lớn.
• Khai báo mảng dp nhỏ hơn giới hạn của n, dẫn đến lỗi truy cập ngoài mảng.