Dynamic Programming Part 6: Tree Problems Involving DP

We look at some dynamic programming problems involving trees. In one problem, the DP function variable is a node (rather than e.g. an array index), and in another problem, we look at solving an optimization problem on an array by finding the optimal index to split the array into subarrays, turning it into a problem about finding an optimal binary expression tree.

[techinterviewsandcompetiti]

def vals(nums, i):
if i == len(nums) or i == -1:
return 1
return nums[i]

def f(i, j, dp, nums):
if i > j:
return 0
if i == j:
return vals(nums, i-1) * nums[i] * vals(nums, i+1)
if (i, j) in dp:
return dp[(i, j)]
bestVal = -1
for k in range(i, j+1):
bestVal = max (bestVal, f(i, k-1, dp, nums) + f(k+1, j, dp, nums) + vals(nums, i-1) * nums[k] * vals(nums, j+1))
dp[(i, j)] = bestVal
return bestVal

class Solution:

def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = {}
return f(0, len(nums) - 1, dp, nums)

[niebhasanneom]

Your channel saved my dynamic programming.

[mallika]

1:03 An easy counter-example to see why simply choosing to pop balloons from smallest to largest value doesn't work, is when the smallest value balloon is at one edge, e.g. [7, 8, 2]

1:27:30 "Number of States is (N^2)/2 maybe, but O(N^2)" - by 2, because we only evaluate for j > i

Almost to the end, I kept thinking not every F(i, j) would be called, because either i would be the first or j the last element!! But i and j are defined on the initial array, and so while that's true of the very first recursive call, subsequently, we will try popping the first element of the 2nd subarray, and the last element of the 1st subarray, so we will already have wanted to evaluated F(i, j) where neither i would be the first or j the last element. I'd already run into this confusion between the original array and the subarrays after stumbling then realizing k doesn't go from 1 to n-1, it goes from i to j; and the value collected isn't just 1*A[k]*1, but A[i-1]*A[k]*A[j+1] - yet I still managed to fall prey to this same confusion!!

[Mohammad-woyi]

As I see it, the formula at 1:20:00 means that we pick the element immediately and not at last (like you were explaining before).

As a result I feel that the formula is not correct because when we pick an element immediately, we should have a mechanism to notify the subproblems that this element is not available anymore in the array (that element can no longer be an adjacent element for any of subproblems).

(P.S: Thank you for this awesome playlist. This really helped me a lot to understand DP).

[StudyWithRishiP]

I really liked your videos. Lets do a collaboration.