theVPN's blog

Optimizing a DP problem
By theVPN, history, 3 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can you share the problem link?

→ Reply
»
3 years ago, hide # |
← Rev. 5  
Vote: I like it +3 Vote: I do not like it

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:

  • $$$j \lt i$$$
  • $$$a_j \lt a_i$$$
  • $$$s' + a_i = s$$$

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?

→ Reply