I have the following problem
Given an array of n integers called a (n <= 10^3 and |a[i]| <= 10^4). Given an integer M, count the number of increasing subsequenes such that the sum of their elements equal to M.
E.g: with the input
6 11
7 1 4 3 5 6
The results should be 2 since 2 subsequences (1,4,6) and (5,6) satisfy the conditions.
I have approached an algorithm that results in O(n^2*m) complexity. But still, I'm wondering is there an even better way to optimize this algorithm? Hopefully you guys can help me
Can you share the problem link?
If the state is $$$dp(i, s)$$$ for subsequence with sum $$$s$$$ end at $$$i$$$ you probably came up with the transition $$$dp(j, s')$$$ to $$$dp(i, s)$$$ if:
Naively by enumerating all $$$j \lt i$$$ it will take $$$\mathcal{O}(n^2m)$$$, which matches your analysis.
But see, if values of $$$dp(j, s')$$$ are sorted by value of $$$a_j$$$ the transitions just come from a prefix of it. So you need the data structure: update value, query prefix. It's done with fenwick tree. Now transition is $$$\mathcal{O}(\log n)$$$ for $$$\mathcal{O}(nm\log n)$$$ time. Hopefully $$$m$$$ is small enough?