在本文中，我們將使用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;
}3
在這種方法中，至少包含一次或不包含任何權重為M的邊。其次，我們計算了路徑的總權重，如果它等於W。
我們將答案增加一，將該路徑標記為已訪問，繼續通過所有可能的路徑，並至少包含一條權重大於或等於M的邊。
在本文中，我們使用動態規劃解決了在k叉樹中找到權重為W的路徑數的問題，時間複雜度為O(W*K )。
我們也學習了解決這個問題的C 程式和完整的方法（普通和高效）。
以上是使用C++找到K叉樹中權重為W的路徑數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
