I Maximum score of big balloon
1. Corresponding letecode link
The maximum score of ballooning_ Niuke Tiba_ Niuke (nowcoder.com)
2. Title Description:
3. Problem solving ideas
Personally, I think this problem is extremely difficult: the main steps are as follows:
1. Preprocessing: to facilitate processing, you can add a sentinel 1 at both ends of the num array, that is, num[0]= and num[N]=1, where N is the length of the array.
2. Define the recursive function func (vector<int>&num, Int l, int r) whose recursive meaning is the maximum score that can be obtained within the range of num [l..... R]
3. We found that when we try the possibility, the score of each position is related to its left state and right state, which makes the possibility of trying very much, so. We can try like this. We try to get the maximum score of each waste at the end of the explosion.
4. Note: the recursive function func must ensure that the number at the position of a subtext num[l-1] must not explode and the number at the position of num[r+1] must not explode. Otherwise, do not adjust this function
First, add a 1 at the beginning and end to facilitate code implementation. Next we can generate possibilities
We tried to blow up the cur position. Note: (if an interval is (left,right), then there is no balloon in this interval.). We try this at every location. The final answer must be in it. We just need to update it.
4. Corresponding code:
#include<iostream>
#include<vector>
using namespace std;
//The secondary arr[L-1] position and arr[R+1] position of the submersible must not explode
//Maximum score within the range of recursive meaning arr[L.....R]
int func(vector<int>& arr, int L, int R) {
if (L == R) { //Only one balloon explodes
return arr[L] * arr[L - 1] * arr[R + 1];
}
//Possibility 1: finally explode the balloon at arr[L]
int p1 = func(arr, L + 1, R) + arr[L] * arr[L - 1] * arr[R + 1];
//Possibility 2: finally explode the balloon at arr[R]
int p2 = func(arr, L, R - 1) + arr[R] * arr[L - 1] * arr[R + 1];
int ans = max(p1, p2);
for (int i = L + 1; i < R; i++) {//Generate the maximum score that can be obtained by the final detonation of each position within the range of [L+1,R-1]
int left = func(arr, L, i - 1); //Blow up the left part
int right = func(arr, i + 1, R); //Blow up the right part
int cur = arr[i] * arr[L - 1] * arr[R + 1]; //Explode current position
ans = max(ans, cur + left + right);//Update answers
}
return ans;
}
int maxCoins(vector<int>& nums) {
int N = nums.size();
vector<int>arr(N + 2);
for (int i = 0; i < N; i++) {
arr[i + 1] = nums[i];
}
arr[0] = arr[N + 1] = 1;
dp.resize(N + 1, vector<int>(N + 1, -1));
return func(arr, 1, N);
}
int main() {
int N;
cin >> N;
vector<int>arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
cout << maxCoins(arr) << endl;
return 0;
}2. Memorized search code:
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>>dp;
//The secondary arr[L-1] position and arr[R+1] position of the submersible must not explode
//Maximum score within the range of recursive meaning arr[L.....R]
int func(vector<int>& arr, int L, int R) {
if (L == R) { //Only one balloon explodes
return arr[L] * arr[L - 1] * arr[R + 1];
}
if (dp[L][R] != -1) {
return dp[L][R];
}
//Possibility 1: finally explode the balloon at arr[L]
int p1 = func(arr, L + 1, R) + arr[L] * arr[L - 1] * arr[R + 1];
//Possibility 2: finally explode the balloon at arr[R]
int p2 = func(arr, L, R - 1) + arr[R] * arr[L - 1] * arr[R + 1];
int ans = max(p1, p2);
for (int i = L + 1; i < R;
i++) {//Generate the maximum score that can be obtained by the final detonation of each position within the range of [L+1,R-1]
int left = func(arr, L, i - 1); //Blow up the left part
int right = func(arr, i + 1, R); //Blow up the right part
int cur = arr[i] * arr[L - 1] * arr[R + 1]; //Explode current position
ans = max(ans, cur + left + right);//Update answers
}
dp[L][R] = ans;
return ans;
}
int maxCoins(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
int N = nums.size();
vector<int>arr(N + 2);
for (int i = 0; i < N; i++) {
arr[i + 1] = nums[i];
}
arr[0] = arr[N + 1] = 1;
dp.resize(N + 1, vector<int>(N + 1, -1));
return func(arr, 1, N);
}
int main() {
int N;
cin >> N;
vector<int>arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
dp.resize(N + 1, vector<int>(N + 1, -1));
cout << maxCoins(arr) << endl;
return 0;
}Dynamic planning with strict location dependence:
#include<iostream>
#include<vector>
using namespace std;
int maxCoins(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
int N = nums.size();
vector<int>arr(N + 2);
for (int i = 0; i < N; i++) {
arr[i + 1] = nums[i];
}
arr[0] = arr[N + 1] = 1;
vector<vector<int>>dp(N + 2, vector<int>(N + 2));
for (int i = 1; i <= N; i++) {
dp[i][i] = arr[i] * arr[i - 1] * arr[i + 1];
}
for (int L = N; L >= 1; L--) {
for (int R = L + 1; R <= N; R++) {
int ans = max(arr[L - 1] * arr[L] * arr[R + 1] + dp[L + 1][R],
arr[L - 1] * arr[R] * arr[R + 1] + dp[L][R - 1]);
for (int i = L + 1; i < R; i++) {
int left = dp[L][i - 1];
int right = dp[i + 1][R];
int cur = arr[i] * arr[L - 1] * arr[R + 1];
ans = max(ans, left + right + cur);
}
dp[L][R] = ans;
}
}
return dp[1][N];
}
int main() {
int N;
cin >> N;
vector<int>arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
cout << maxCoins(arr) << endl;
return 0;
}II Boolean operation
1. Corresponding letecode link
Interview question 08.14 Boolean operation LeetCode
2. Title Description:
3. Problem solving ideas:
1. Try to calculate the number of true or false methods that can be obtained at the end of each symbol.
2. Define the recursive function Info*func(str,L,R) as the number of methods whose str is true and false within the range of [l... R]. And if the L and R positions are not 0, they are 1. Please see the code for details
4. Corresponding code
class Solution {
public:
struct Info {
Info(int tr, int tf) {
t = tr;
f = tf;
}
int t;//t represents the number of methods that are true
int f;//Number of methods represented as false
};
int countEval(string s, int result) {
dp.resize(s.size(), vector<Info*>(s.size(), NULL));
Info* ret = func(s, 0, s.size() - 1);
return result == 1 ? ret->t : ret->f;
}
//L...... On R, l and R must be either 0 or 1
Info* func(const string& str, int L, int R) {
int t = 0;
int f = 0;
if (L == R) {
t = str[L] == '1' ? 1 : 0;
f = str[L] == '0' ? 1 : 0;
}
else {
//Be sure to save the underlying lines of recursion. The positions of L and R are either 0 or 1
for (int Split = L + 1; Split < R;
Split += 2) { //Try the number of methods that can get the result by the last operation of each symbol
Info* leftInfo = func(str, L, Split - 1);
Info* rightInfo = func(str, Split + 1, R);
int a = leftInfo->t;
int b = leftInfo->f;
int c = rightInfo->t;
int d = rightInfo->f;
switch (str[Split]) { //Classify and calculate according to the last symbol
case'&':
t += a * c;
f += b * c + b * d + a * d;
break;
case'|':
t += a * c + a * d + b * c;
f += b * d;
break;
case '^':
t += a * d + b * c;
f += a * c + b * d;
break;
}
}
}
Info* ans = new Info(t, f);
return ans;
}
};Mnemonic search:
class Solution {
public:
struct Info {
Info(int tr, int tf) {
t = tr;
f = tf;
}
int t;
int f;
};
vector<vector<Info*>>dp;
int countEval(string s, int result) {
dp.resize(s.size(), vector<Info*>(s.size(), NULL));
Info* ret = func(s, 0, s.size() - 1);
return result == 1 ? ret->t : ret->f;
}
//L...... On R, l and R must be either 0 or 1
Info* func(const string& str, int L, int R) {
if (dp[L][R]) {
return dp[L][R];
}
int t = 0;
int f = 0;
if (L == R) {
t = str[L] == '1' ? 1 : 0;
f = str[L] == '0' ? 1 : 0;
}
else {
cout << L << " " << R << endl;
for (int Split = L + 1; Split < R; Split += 2) {
Info* leftInfo = func(str, L, Split - 1);
Info* rightInfo = func(str, Split + 1, R);
int a = leftInfo->t;
int b = leftInfo->f;
int c = rightInfo->t;
int d = rightInfo->f;
switch (str[Split]) {
case'&':
t += a * c;
f += b * c + b * d + a * d;
break;
case'|':
t += a * c + a * d + b * c;
f += b * d;
break;
case '^':
t += a * d + b * c;
f += a * c + b * d;
break;
}
}
}
Info* ans = new Info(t, f);
dp[L][R] = ans;
return ans;
}
};