This was the question that was asked in hackwithinfy. I was told this was a dp question but can anybody implement it? I am not able to get the clue.
The government of Imagineland constructed a new road to connect 2 different cities. This road currently doesn’t have any light poles to illuminate it. The government wants to add new light poles to the street to rectify this issue.
To help the government make the budget for this project, you are tasked with calculating the total number of different possible configurations of putting light poles such that the whole street is illuminated.
It is given that the street is divided into N plots of land which have the same size. You can put one light pole in one plot of land.
Each light pole illuminates the plot that it is on, and it illuminates K plots to the right of it. You can put as many light poles as you want as long as the whole street is illuminated.
Calculate the total number of different possible light pole configurations. Since the answer can be very large, return the answer modulo 10^9+7.
Note: Two configurations are considered different if here’s a plot of land that has a light pole in the first configuration but doesn’t have one in the second configuration.
Input:
4
4
Output: 8
Input
4
1
Ouput:5
187
30
Output: 723327646