But this dp is still O(N2⋅K). We can optimize this dp, coming to dp*[j]=dp[i−1][j−1]+dp[i−2][j−1]+dp[i−1][j]. pre-compute this dp for all 1≤n,k≤1000, and we can for fixed N,K sum up all values dp*[K],K i≤N.
Why? How? Where did this derivation come from?
What I mean to point out is, dont you think its highly weird to just write the recurrence here as “we can optimize this to ___” and skip the part of how we got that? No offence, but I feel skipping of that part shouldnt be done.
BTW - Anguepa’s answer here is a very neat explanation of how to derive the recurrence - https://math.stackexchange.com/questions/2945440/number-of-ways-to-select-k-non-adjacent-boxes-in-a-2-times-n-board/2945878