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!

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.