使用 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++程序以及解决此问题的完整方法（正常和高效）。