I was practising [C. k-Tree](https://mirror.codeforces.com/problemset/problem/431/C). 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;↵
}↵
↵
↵
~~~~~↵
↵
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;↵
}↵
↵
↵
~~~~~↵
