使用C++找到K叉树中权重为W的路径数量

WBOY 转载: 2023-09-16 18:09:04 391浏览

在本文中，我们将使用C++来计算K叉树中权重为W的路径数量。我们已经给出了一个K叉树，它是一棵每个节点有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) // 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;
}