Problem: We are given N boxes in a row. We have to place minimum balls in boxes such that each M consecutive boxes have at least K balls. Find the number of ways of placing balls in boxes. Given N, M, K. 1<=K<=M<=50 M<=N<=10^9 If N = 3, M = 2, K = 1 Ans : 1 If N = 6, M = 3, K = 2 Ans: 6 What is the state of DP ?
Can you please post the question link ?
Sorry. It's not on public IP.
You can't use dynamic programming. The problem will be solved using matrix exponentiation.
are you sure if N = 3, M = 2, K = 1 Ans : 1 ?
all boxes must have at least 1 ball ? you didn't say that !
did you mean each M consecutive boxes or at least one ? ? ? you did not say any thing !