This is my first blog post here and also this is the first dp problem I was able to solve by myself. So, I thought I should celebrate it by publishing a blog entry. Here it goes..., We have to find the sum of the numbers(range[1...k]) such that their sum forms n. Also it's given that there must be at least one entry with value >=d. So this is equivalent to...
Required Number of Paths = (total number of paths which sum to n using range[1...k]) - (total number of paths which sum to n using range[1...d-1])
Each of the two subproblems on the R.H.S can be individually solved using dp. You can see the solution here
PS: Feel free to suggest improvements or show up bugs :D Thank You..,
Update 1: From Michael Kirsche's explanation I have improved my implementation which can be found here. Thank You mkirsche
DP can be a really hard concept to wrap your head around, so first of all congrats on solving it. :) Also, I do have one suggestion for improvement on this problem for making it run faster. In your DP, the first dimension seems to be the depth in the tree, but this is not actually important. You can create a one-dimensional such that dp[i] is the number of paths with sum of i, regardless of depth. Then, dp[0] is 1, and each of the other values can be computed according to the following loop, trying all possible edges to be the last edge on the path: for(j = 1; j<= min(i, k); j++) dp[i] += dp[i-j]; Then the runtime is O(n*k) instead of O(n*n*k). Not necessary for the given bounds of 100 for n and k, but if the bounds were as high as 5000 your approach would be too slow.
do you know there's pure math solution for this problem? "Total number of paths which sum to n using range[1...k]" equals to n-th Fibonacci K-step number. Can you prove it?
I am sincerely unaware of that. Can you give me references, also can you explain what is an "nth Fibonacci K-step number" or some references related to that too..,
Fibonacci 2-step number: Fi = Fi - 1 + Fi - 2
Fibonacci 3-step number: Fi = Fi - 1 + Fi - 2 + Fi - 3
Fibonacci N-step number: Fi = Fi - 1 + Fi - 2 + ... + Fi - n
someone's code: 6684479
This is a simple DP.
Lets say dp[N] = "Total number of paths which sum to n using range[1...k]".
So if we can pich [1...k] each step => dp[N] = dp[N-1] + dp[N- 2] + dp[N-...] + dp[N-k].
So this is actually (as you call it) — Fibonacci k-step number.
Also consider
Fi = i-th Fibonacci k-step numberFi = Fi-1 + Fi-2 ... + Fi-kandFi+1 = Fi + Fi-1 + ... + Fi-k+1Lets subtract
Fi+1byFi=>
Fi+1 - Fi = Fi - Fi-k=>Fi+1 = (2 * Fi) - (Fi-k)for every "i" and "k".So for every N-th Fibonacci K-step number:
Fi = 2 * Fi - Fi-k-1