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.