I recently encountered a DP question at least that's what i could make up for it. It goes :
You are given two numbers N, P, find the number of tuple of size N such that the product of adjacent numbers are at most P. Two tuples are considered different if the order of elements are different in them. Since the number can be large output it modulo 1e9+7.
Constraints : 2 <= N <=100 1 <= P <=1e9
Please help me with this problem and suggest some problems like this, if you can. Thanks.
Slow solution: $$$dp_{i,j} =$$$ number of ways with length $$$i$$$ and last element $$$j$$$.
Faster solution: do you need the exact value of $$$j$$$? For example, if $$$k = 10$$$, any $$$j$$$ in $$$[6, 10]$$$ gives the same value of $$$dp_{i,j}$$$ and the same transitions (why?). Can you prove that you only have to consider $$$O(\sqrt p)$$$ distinct values of $$$j$$$?
Similar problems:
(can anyone suggest easier problems?)
Same problem here with editorial: https://atcoder.jp/contests/abc132/tasks/abc132_f