Contest

Problem

I realised this problems requires DP, but could not form the recurrence relation. It would be great if any one could explain it a bit.

You can iterate through all the possible values and store the values in 2D matrix say

`dp[51][500001]`

where `dp[i][j]`

means number of ways to reach total sum `N`

from day number`i`

and when current sum is `j`

. My code

It can be done using linear dp as well. You need to construct a dp[N+1] where dp[I] contains the number of ways you can reach the total sum I. You can then iterate over k days and keep updating dp[N+1]. My solution