Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### VandanRogheliya's blog

By VandanRogheliya, history, 9 days ago, , 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);
}

}  Comments (9)
 » 9 days ago, # | ← Rev. 2 →   [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 + 12nd way: 2 + 13rd way: 1 + 2So 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; } 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).
 » 9 days ago, # | ← Rev. 2 →   You can do this using dp.Suppose you want to make sum i using numbers from 1 to d.For i=0: dp=number of ways = 1(using no numbers at all) [base case]Then for any arbitrary idp[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 differentYou 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?
•  » » » 9 days ago, # ^ | ← Rev. 3 →   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=2dp=1 corresponds to selecting no numbers [base case]dp=dp[1-1]=dp=1 corresponds to taking only 1 (this is the only way to make 1)dp=dp[2-1] (corresponding to 1+1) + dp[2-2] (corresponding to only 2) = dp+dp=1+1=2dp=dp[3-1] (corresponding to 1+1+1 and 2+1) + dp[3-2] (corresponding to 1+2) = dp+dp=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!
 » 0
 » 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.