Trilogy to solve the problem of playing chess first and then

1. subject

Two people play chess , Given an array Arr={1,4,9,2,10,7}; Two people can only take elements from both ends of the array , Get the score of the winner ;

First, make it clear , The best solution of this game is to win first , But if two people play games in real life, it's not necessarily

2. Violent recursive solution

• Ideas
  Want to get the score of the winner , The winner must be one of the two , Either a wins or B wins ; When a wins, he may be the first or the second , Then it can be regarded as a pioneer ( Second hindhand ) The score obtained is the same as that of the second hand ( B first ) The maximum of the scores obtained ;
  explain ： function f(Arr,L,R) Represents in the array [L,R] From the beginning to the end of the game , A first hand Can also The maximum score obtained ; function s(Arr,L,R) Represents in the array [L,R] From the beginning to the end of the game , Posterior nail hand Can also The maximum score obtained ;

• code

int  f(vector<int>& Arr, int L, int R)
{
    
	if (L == R)
		return Arr[L];
	else
		return max(Arr[L] + s(Arr, L + 1, R,dp), Arr[R] + s(Arr, L, R - 1));
}

int s(vector<int>& Arr, int L, int R)
{
    
	if (L == R)
		return 0;
	else
		return max(f(Arr, L + 1, R, dp), f(Arr, L, R - 1, dp));
}

• 3. Memory search solution

Solution 1 has repeated calculation , Suppose the state array , Record the status reached

• code

#include<iostream>
#include<vector>
using namespace std;

class QQ
{
    
public:
	int  f(vector<int>& Arr, int L, int R, vector<vector<int>>& dp)
	{
    
		if (dp[L][R] != -1)
			return dp[L][R];
		if (L == R)
			dp[L][R] = Arr[L];
		else
			dp[L][R] = max(Arr[L] + s(Arr, L + 1, R,dp), Arr[R] + s(Arr, L, R - 1,dp));
		return dp[L][R];
	}

	int s(vector<int>& Arr, int L, int R, vector<vector<int>>& dp)
	{
    
		if (dp[L][R] != -1)
			return dp[L][R];
		if (L == R)
			dp[L][R] = 0;
		else
			dp[L][R] = max(f(Arr, L + 1, R, dp), f(Arr, L, R - 1, dp));
		return dp[L][R];
	}
};


int main()
{
    
	QQ qq;
	vector<int> Arr = {
     3,100,2,50 };
	int L = 0;
	int R = Arr.size();
	
	vector<vector<int>> dp(R, vector<int>(R,-1));


	int res = qq.s(Arr, L, R - 1,dp);
	cout << res << endl;
	return 0;
}

4. Strict table structure solution

Define two tables f and s, First, determine the position in the table where the value can be directly obtained , Then determine the location dependency , Determine the traversal order ;

• code

void code2(vector<int>& Arr, vector<vector<int>>& f, vector<vector<int>>& s)
{
    
	for (int i = 0; i < Arr.size(); i++)
		f[i][i] = Arr[i];
	int row = 0;
	int col = 1;
	while (col < Arr.size())
	{
    
		int m = row;
		int n = col;
		while (n < Arr.size())
		{
    
			f[m][n] = max(Arr[m] + s[m + 1][n], Arr[n] + s[m][n - 1]);
			s[m][n] = max(f[m][n - 1], f[m + 1][n]);
			m++;
			n++;
		}
		col++;
	}
}
int main()
{
    
	vector<int> Arr = {
     3,100,70,50 };
	int R = Arr.size();
	vector<vector<int>> f(R, vector<int>(R, 0));
	vector<vector<int>> s(R, vector<int>(R, 0));
	code2(Arr, f, s);
	int res = max(f[0][R-1], s[0][R-1]);
	cout << res << endl;
	return 0;
}