wittybull7's blog

Need help for a DP Problem or maybe not a DP problem
By wittybull7, history, 3 years ago, In English

Given an array of integers

You need to make maximum profit by removing numbers until only one number remains in array.

Profit when you remove an array element i = arr[i-1] * arr[i] * arr[i+1]

after the above operation ith element is removed from array

corner elements will have profit = corner element * adjacent element

Example : [3, 5, 1, 8, 2]

  1. Remove 8 : profit = 1*8*2, array = [3, 5, 1, 2]
  2. Remove 1 : profit = 1*8*2 + 5*1*2 array = [3, 5, 2]

and so on..

Asked in an interview, no source available
Tried searching internet, no help found

UPD -> Link : https://leetcode.com/problems/burst-balloons/

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

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

Wouldnt the greedy approach work for this one?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it would not arr = [2 1 3 5]
    you need to remove 1, then 3, then 5.

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

What are the constraints? I might have an O(n^2) dp solution.

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

dp[i] — answer, if we can delete only first I elements.

so dp[0] = a[0]*a[1]

how to calc dp[i]?

dp[i] = max(dp[i-1], (i>1?dp[i-2]:0)+a[i-1]*a[i]*a[i+1])

so answer is dp[n-1]

i'm not sure if it's correct

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This is the exact same problem: link

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

Sorry the last one is incorrect...

We still set $$$dp[i][j]$$$ as the maximum profit for range $$$[i,j]$$$.

Thus,we can split the range $$$[i,j]$$$ into $$$3$$$ parts:$$$dp[i][k-1],dp[k+1][j]$$$ and the profit of $$$d[i-1]\times d[k]\times d[j+1]$$$.

So $$$dp[i][j]=dp[i][k-1]+dp[k+1][j]+d[i-1]\times d[k] \times d[j+1]$$$ for all $$$k\in[i,j]$$$,note that if $$$i>j$$$,$$$dp[i][j]$$$ should be $$$0$$$.

Complexity is $$$O(n^3)$$$.

→ Reply