# Untitled

unknown
c_cpp
7 months ago
1.6 kB
19
Indexable
Never
```// AMAN JAIN MCA 2nd year

class Solution {
public:

int getMin(vector<int>& nums, vector<vector<int>>& dp, int x, int left, int right, int totalOperations) {
if(x == 0) {
}
else if(left > right) {
return -1;
}
else if(dp[left][right] != -2) {
return dp[left][right];
}
else {
int leftSubtree = -1, rightSubtree = -1;
if(x - nums[left] >= 0) {
leftSubtree = getMin(nums, dp, x - nums[left], left + 1, right, totalOperations + 1);
}
if(x - nums[right] >= 0) {
rightSubtree = getMin(nums, dp, x - nums[right], left, right - 1, totalOperations + 1);
}
if(leftSubtree == -1 && rightSubtree == -1) {
dp[left][right] = -1;
return dp[left][right];
}
else if(leftSubtree == -1 || rightSubtree == -1) {
dp[left][right] = leftSubtree == -1 ? rightSubtree : leftSubtree;
return dp[left][right];
}
else {
dp[left][right] = min(leftSubtree, rightSubtree);
return dp[left][right];
}
}
}

int minOperations(vector<int>& nums, int x) {
int N = nums.size(), totalOperations = 0, left = 0, right = N - 1;
vector<vector<int>> dp(N, vector<int>(N, -2));
return getMin(nums, dp, x, left, right, totalOperations);
}
};```