在本文中，我们将使用C++来计算K叉树中权重为W的路径数量。我们已经给出了一个K叉树，它是一棵每个节点有K个子节点且每条边都有一个权重的树，权重从1到K递减从一个节点到其所有子节点。
我们需要计算从根节点开始的累积路径数量，这些路径具有权重为W且至少有一条边的权重为M。所以，这是一个例子：
Input : W = 4, K = 3, M = 2 Output : 6
在给定的问题中，我们将使用dp来减少时间和空间复杂度。通过使用记忆化，我们可以使我们的程序更快，并使其适用于更大的约束。
方法
在这个方法中，我们将遍历树，并跟踪使用或不使用至少为M的权重的边，且权重等于W，然后我们增加答案。
立即学习“C++免费学习笔记（深入）”；
输入
#include <bits/stdc++.h>
using namespace std;
int solve(int DP[][2], int W, int K, int M, int used){
if (W < 0) // if W becomes less than 0 then return 0
return 0;
if (W == 0) {
if (used) // if used is not zero then return 1
return 1; //as at least one edge of weight M is included
return 0;
}
if (DP[W][used] != -1) // if DP[W][used] is not -1 so that means it has been visited.
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); // if the condition is true
//then we will change used to 1.
else
answer += solve(DP, W - i, K, M, used);
}
return answer;
}
int main(){
int W = 3; // weight.
int K = 3; // the number of children a node has.
int M = 2; // we need to include an edge with weight at least 2.
int DP[W + 1][2]; // the DP array which will
memset(DP, -1, sizeof(DP)); // initializing the array with -1 value
cout << solve(DP, W, K, M, 0) << "\n";
return 0;
}输出
3
上述代码的解释
在这种方法中，至少包含一次或不包含任何权重为M的边。其次，我们计算了路径的总权重，如果它等于W。
我们将答案增加一，将该路径标记为已访问，继续通过所有可能的路径，并至少包含一条权重大于或等于M的边。
结论
在本文中，我们使用动态规划解决了在k叉树中找到权重为W的路径数量的问题，时间复杂度为O(W*K)。
我们还学习了解决这个问题的C++程序和完整的方法（普通和高效）。
