k-tree

This is one of the more complex problems so looking at my solution while reading the explanation would be ideal! The problem statement is here. This problem, the K-tree is perhaps one of my favorite problems for dynamic programming and soon I hope you see why as well. So we start out this problem by noticing that it says at least d. Hence, we want to find solutions that contain a weight greater than or equal to d. We know that for each sum there are solutions that have do not contain the weight d (or greater) and solutions that do contain the weight d (or greater) . So we create a 2-D ARRAY to keep track of this via dynamic programming. We will create a dp[n][x] array, where x is of size 2, and goes from 0 to 1. In dp[x][y] if y == 0, it tells you how many solutions there are to get the sum x without using weights d or bigger. If y == 1 then dp[x][y] tells you how many solutions there are to get the sum x with using weights d or bigger. Why we do this will become clear in a second.

So now we say that for dp[0][0] = 1 because 0 < d. and dp[0][1] = 0 because 0 cannot be >= d. Now we start iterating from (dp[1][0] and dp[1][1]) to (dp[n][0] and dp[n][1]). We know that the maximum singular weight of a vertex is k. So for each i in between 1-n we then iterate through a j from 1-k (j < i) . If j < d, it means that we are using a weight less than d so our dp[i][0] should += dp[i-j][0], to get the number of possible solutions using j + i- j that don’t contain the weight d (or greater), and our dp[i][1] should += dp[i-j][1] to have all the possible sums that do contain the weight d or greater. If j >= d, it means that we are currently using a weight that is greater than or equal to j so our dp[i][1] should += (dp[i-j][0] {this is all the solutions that don’t contain d or greater, but because our j is d or greater we can use all of these sums as well} + dp[i-j][1] { all previous sums of i – j that contain d}. If we keep on doing this process over and over again we will get a value for dp[n][1] a solution that tells us all possible ways to get the sum of n using a weight greater than or equal to d.