Tìm số đường đi trọng số W trong cây K-ary bằng C++

Cho cây K-ary (mỗi nút có K con), cạnh từ nút cha đến các con có trọng số từ 1 đến K. Đếm số đường đi bắt đầu từ gốc có tổng trọng số = W và chứa ít nhất một cạnh trọng số ≥ M.

Ví dụ

Input: W=4, K=3, M=2 Output: 6

Phương pháp Dynamic Programming

Dùng DP với memoization: dp[w][used] = số đường đi còn lại trọng số w, used=1 nếu đã dùng cạnh ≥ M. Hàm đệ quy:

• Nếu w < 0: return 0
• Nếu w == 0: return used (phải đã dùng cạnh ≥ M)
• Duyệt cạnh i = 1..K: nếu i ≥ M thì used' = 1, đệ quy dp[w-i][used']

Mã nguồn C++

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

int solve(int dp[][2], int W, int K, int M, int used) {
    if (W < 0) return 0;
    if (W == 0) return used ? 1 : 0;
    if (dp[W][used] != -1) return dp[W][used];

    int ans = 0;
    for (int i = 1; i <= K; i++) {
        if (i >= M)
            ans += solve(dp, W - i, K, M, 1);
        else
            ans += solve(dp, W - i, K, M, used);
    }
    return dp[W][used] = ans;
}

int main() {
    int W = 3, K = 3, M = 2;
    int dp[W + 1][2];
    memset(dp, -1, sizeof(dp));
    cout << solve(dp, W, K, M, 0) << "\n";
    return 0;
}

Kết quả

3

Giải thích

DP state: trọng số còn lại W và cờ used (đã dùng cạnh ≥ M chưa). Mỗi bước thử K cạnh, cập nhật used nếu cạnh ≥ M. Memoization tránh tính lại. Độ phức tạp O(W·K).

Kết luận

Bài viết giải quyết bài toán đếm đường đi trong cây K-ary với điều kiện trọng số bằng DP + Memoization. Mã C++ ngắn gọn, hiệu quả. Có thể chuyển sang C, Java, Python.