Hello everyone, I have been struggling for two weeks now trying to solve this problem

I know it has to do with some combinatorics. Muy first thought was something like (k-2)^N por something Of the like, but that clearly doesnt work.

If have be en writing things down, but i cant see the pattern. I know also it has to be linear with respect to n.

Thanks a bunch!!!

Hello guys, this is my first post, and yes, it is asking for some help.

I am trying to solve this problem using dp. I know there is a greedy solution, but I would really like to solve it using dp. The thing is that the solution I devised uses 1000*1000*1000 in space.

Does anyone know a better way to solve it using dp.

Thanks for your help.