niti94's blog

A DP Problem..
By niti94, 10 years ago, In English

I was trying to solve This problem of Google APC 2015.

I did a o(n^4) Dp for finding the maximum number of elements that can be removed, keeping the starting and ending index of the array(say i,j) and two loops for transition in a state for finding all possible triplets in i to j range.

Let (a,b,c) is a triplet possible such that b-a=c-b=k where i<=a<=b<=c<=j

dp[i][j]=max(dp[i][j],3+dp[i][a-1]+dp[a+1][b-1]+dp[b+1][c-1]+dp[c+1][j])

Can someone give a better complexity solution...

Thanks

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

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

My DP solution:

canRemove(i, j) = (canRemove(i, k) and canRemove(k + 1, j)) or (satisfy(i, k, j) and canRemove(i + 1, k - 1) and canRemove(k + 1, j - 1))

length(i) = min(length(i - 1) + 1, length(j) if canRemove(j + 1, i))

The complexity is O(N^3).

→ Reply