I was practising C. k-Tree. I want to solve it by finding the difference between f(n,k) and f(n,d-1) where f will return the number of ways to break n into a sum of integers from 1 to k.
Can someone please link the resources for an iterative solution or explain it?
Thank you!
Edit: Making it less confusing:
Example:
I want to find the number of ways to make sum n=3 from using integers 1 to k=2.
1st way: 1 + 1 + 1
2nd way: 2 + 1
3rd way: 1 + 2
So total ways are 3.
Note: I can not use only 3 because it is more than k=2. If k=3 then I can also use only 3 and get 4 ways.
I can do this by recursion like this:
ll recFun(ll k, ll n, ll sum = 0) {
if (sum == n) {
return 1;
} else if (sum > n) return 0;
ll total = 0;
FO(i, k) {
total += recFun(k, n, sum+i+1);
}
return total;
}
[deleted]
Sorry, I think my blog is a bit confusing. Let me explain the doubt with an example.
I want to find number of ways to make sum n=3 from using integers 1 to k=2.
1st way: 1 + 1 + 1
2nd way: 2 + 1
3rd way: 1 + 2
So total ways are 3.
Note: I can not use only 3 because it is more than k=2. If k=3 then I can also use only 3 and get 4 ways.
I can do this by recursion like this:
I want to know how to do this in an iterative way using memoization. I will also add this OP to make it less confusing.
Auto comment: topic has been updated by VandanRogheliya (previous revision, new revision, compare).
You can do this using dp.
Suppose you want to make sum i using numbers from 1 to d.
For i=0:
dp[0]=number of ways = 1(using no numbers at all) [base case]
Then for any arbitrary i
dp[i] = sum(dp[i-j]) for all j from 1 to min(d,i) (bcoz u cant use a number greater than i to make sum i)
this works bcoz here order matters 1+2 and 2+1 are different
You can see my submission for implementation Click
Thank you for the explanation but I do not understand why dp[i] = sum(dp[i-j]) works?
What is the intuition behind it?
Okay, so we are making a number i using the numbers from 1 to d right. Suppose i=a1+a2+a3+...+ap+x where all numbers ai and x belongs to [1,d]. Now focus on the last number x, it(again) can be anything belonging to [1,d], so we consider all possible options for x that will guarantee that we count all possible ways to sum to i.
so we iterate over [1,d] (for now i am assuming i>=d else it would be min(i,d))
suppose currently we are considering x=j, now to calculate the number of ways you can make i such that last number = j, observe that you can add the number j to all the number of ways you can make i-j. hence dp[i-j].
Hence dp[i] = sum over all dp[i-j] where j belongs to [1,min(d,i)]
Let's take your example n=3,d=2
dp[0]=1 corresponds to selecting no numbers [base case]
dp[1]=dp[1-1]=dp[0]=1 corresponds to taking only 1 (this is the only way to make 1)
dp[2]=dp[2-1] (corresponding to 1+1) + dp[2-2] (corresponding to only 2) = dp[1]+dp[0]=1+1=2
dp[3]=dp[3-1] (corresponding to 1+1+1 and 2+1) + dp[3-2] (corresponding to 1+2) = dp[2]+dp[1]=2+1=3
Hence number of ways you can make 3 using 1 and 2 is 3.
Hope my explanation was clear :)
The point about making i from adding j and i-j did the trick! Thank you so much!
Well, we can solve this with a naive Dp-approach in $$$O(n\cdot k)$$$ time and $$$O(n)$$$ Space.
Let $$$dp[n]$$$ be the amount you want. If the last taken number is $$$i$$$, then we remain with $$$n-i$$$, and this gives us the transition: $$$dp[n]=\sum_{i=1}^k dp[n-i]$$$.
We can use sliding window technique to achieve $$$O(n)$$$ time and $$$O(k)$$$ space.
Also, if $$$n$$$ is very big and $$$k$$$ is small enough (about 300) we can use matrix power to get a solution in $$$O(k^3 \cdot \log n)$$$ time and $$$O(k^2)$$$ space.