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 numberi 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