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