the below code is also not working for 5th test case
target = [1] + target +[1]
dp ={}
def dfs(l, r):
if l > r :
return 0
if (l,r) in dp:
return dp[(l,r)]
dp[(l,r)] = 0
for i in range(l, r+1):
coins = target[l-1]* target[i] * target[r+1]
coins += dfs(i+1, r) + dfs(l, i-1)
dp[(l,r)] = max(dp[(l,r)], coins)
return dp[(l,r)]
return dfs(1, len(target)-2)
Is something wrong with Test#3? Please help with this code.
long long dfs(vector<int> & w, vector<vector<int>> & dp, int l, int r) {
if(l > r) return 0;
if(dp[l][r]) return dp[l][r];
int maxCoin = 0;
for(int i = l + 1; i < r; i++) {
int coin = w[l] * w[i] * w[r];
int left = dfs(w, dp, l, i);
int right = dfs(w, dp, i, r);
maxCoin = max(maxCoin, coin + left + right);
}
return dp[l][r] = maxCoin;
}
long long festival_game(std::vector<int> target) {
// WRITE YOUR BRILLIANT CODE HERE
vector<int> nums;
nums.push_back(1);
for(auto val: target) {
nums.push_back(val);
}
nums.push_back(1);
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
return dfs(nums, dp, 0, n - 1);
}
The proposed top-down solution does not seem correct. On line 19, why are we checking to see if l == 0 and if r == target.size() - 1? It wouldn’t we want to check instead if i == 0 / i == target.size() - 1 since that is the target we are currently choosing to shoot. Also, if we shoot a target, is that target still able to be multiplied by if we shoot one of its adjacent targets? The proposed solution makes it seem like they are, but in the examples at the beginning, it seems as though that is not allowed. Just seems a bit inconsistent, but perhaps I am missing something.
While calculating the left and right multipliers why is the bounds check only on 0 and len(target)-1. Shouldn’t it be on the current state l and r instead?
It would be helpful to add an example with a 1 somewhere in the middle. I had the wrong understanding and such an example would have clarified it for me. If a balloon is popped, you ignore that space and use the next unpopped balloon. Their test case of 3 1 5 8 would work:
1 → 3 * 1 * 5 = 15
5 → 3 * 5 * 8 = 120
3 → 1 * 3 * 8 = 24
8 → 1 * 8 * 1 = 8
Total: 167
I had a similar issue with both my solution and the provided one. I was getting timeout errors with both.
For mine, I profiled the code which revealed I was spending a bunch of time making len and max calls.
Once I refactored my code to use n = len(target) and minimized my use of max to once per dp[l][r] instead of for every k, I passed case 5.
i also dont understand why the left multipliers and right multipliers are always constant and not dependent on i
That’s because inside the function we’re dealing with a particular interval
And we imagine that the balloon we pop is the last in this interval
But there are still potentially balloons left to the right and to the left of this interval. And they count as the neighbours to the last one we pop.
Which is static for a particular recursive function call because we call it for an interval from l to r
Took me some time to realise this
dp solution:
def festival_game(target: List[int]) → int:
# create dp with n
n = len(target)
dp = [[0 for _ in range(n)] for _ in range(n)]
# iterate by difference between left_index and right_index
for size in range(n):
# iterate for left index
for l in range(n - size):
# calcualte right index
r = l + size
# handle edge case i-1 and j+1 out of range , use 1 for multiplier
left_multiplier = 1 if l == 0 else target[l-1]
right_multiplier = 1 if r == n-1 else target[r + 1]
# iterate each element k between left and right indexs inclusive
for k in range(l, r + 1):
k_value = left_multiplier * target[k] * right_multiplier
# handle edge case i > k-1 and k+1 > j, both return 0
left = 0 if l > k-1 else dp[l][k-1]
right = 0 if k+1 > r else dp[k+1][r]
dp[l][r] = max(dp[l][r], left + k_value + right)
return dp[0][n-1]
For those confused about the left and right multipliers, this is the reason.
I was also confused because the problem statement implies that when you pop a balloon at i, you check the immediate adjacent balloons at i-1 and i+1. But really, the multiplier values should be the first unpopped balloons to the left and right of the balloon at i.