使用 C++ 在 K-ary 树中找到权重 W 的路径数

在本文中，我们将使用 C++ 计算本文中 K 叉树中权重 W 路径的数量。我们给出了一个 K-ary 树，它是一棵树，其中每个节点都有 K 个子节点，每个边都有一个分配给它的权重，权重从一个节点到它的所有子节点从 1 降到 K。

我们需要计算从根开始的路径的累积数量，这些路径的权重为 W，并且至少有一条边的权重为 M。所以，这是示例 -

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

Output : 6

在给定的问题中，我们将使用 dp 来降低我们的时间和空间复杂度。通过使用记忆化，我们可以使我们的程序更快，并使其可用于更大的约束。

方法

在这种方法中，我们将遍历树并跟踪权重至少为 M 的边（如果使用与否），并且权重等于 W，因此我们增加答案。

输入

#include <bits/stdc++.h>
using namespace std;
int solve(int DP[][2], int W, int K, int M, int used){
   if (W < 0) // 如果 W 小于 0，则返回 0
       return 0;
    if (W == 0) {
        if (used) // 如果使用的不为零则返回 1
           return 1; //因为至少包括权重 M 的一条边
       return 0;
   }
    if (DP[W][used] != -1) // 如果 DP[W][used] 不是 -1，则表示它已被访问。
       return DP[W][used];
    int answer = 0;
   for (int i = 1; i <= K; i++) {
        if (i >= M)
           answer += solve(DP, W - i, K, M, used | 1); // 如果条件为真
                                                    //然后我们将使用更改为 1。
       else
           answer += solve(DP, W - i, K, M, used);
   }
   return answer;
}
int main(){
   int W = 3; // 重量。
   int K = 3; // 一个节点的子节点数。
   int M = 2; // 我们需要包含一个权重至少为 2 的边。
   int DP[W + 1][2]; // DP 阵列，它将
   memset(DP, -1, sizeof(DP)); // 用 -1 值初始化数组
   cout << solve(DP, W, K, M, 0) << "\n";
   return 0;
}

3

以上代码说明

在这种方法中，跟踪权重的任何边缘，M 至少包含一次或不包含一次。其次，我们计算路径的总权重，如果它变得等于 W。

我们将答案加一，将该路径标记为已访问，继续遍历所有可能的路径，并至少包含一条权重大于或等于 M 的边。

结论

在本文中，我们使用动态规划以O(W*K)时间复杂度解决了在 k 叉树中找到权重为 W 的路径数的问题。

我们还学习了针对此问题的 C++ 程序以及解决此问题的完整方法（正常和高效）。