Recursion and recursion

Recurrence

River crossing pawn

River crossing pawn
This question uses dfs And recursion . The time complexity of recursion is better .

The recurrence of this problem is easy .

f[i][j] = f[i-1][j] + f[i][j-1]

There is a bit of trouble during initialization .
1. If the horse is not in the first row or column , Normal handling
2. If the horse is in the first row or column , All the places behind the horse are inaccessible , That is, the number of paths is 0.

notes ： This kind of writing is not good

#include <iostream>

using namespace std;

const int N = 30;

long long f[N][N];
int a, b, c, d;
int dir[8][2] = {
    {
    2, 1},{
    1, 2},{
    -1, 2},{
    -2, 1},{
    2, -1},{
    1, -2},{
    -1, -2},{
    -2, -1}};

int main()
{
    
	cin >> a >> b >> c >> d;
	
	// Deal with the horse taking a step 
	f[c][d] = -1;
	for(int i = 0; i < 8; i++)
	{
    
		int x = c + dir[i][0], y = d + dir[i][1];
		if(x >= 0 && x <= a && y >= 0 && y <= b) f[x][y] = -1;
	}
	
	// Deal with horses in the first row or column 
	// It's a little cumbersome , There's a better way 
	int h = 0;
	for(int i = 0; i <= b; i++)
		if(f[0][i] == -1)
		{
    
			h = i;
			break;
		}
	for(int i = 0; i <= b; i++) 
	{
    
		if(h == 0) f[0][i] = 1;
		else if(i >= h) f[0][i] = -1;
		else f[0][i] = 1;
	}
	
	h = 0;
	for(int i = 0; i <= a; i++)
		if(f[i][0] == -1)
		{
    
			h = i;
			break;
		}
	for(int i = 0; i <= a; i++)
	{
    
		if(h == 0) f[i][0] = 1;
		else if(i >= h) f[i][0] = -1;
		else f[i][0] = 1;
	}
	
	for(int i = 1; i <= a; i++)
		for(int j = 1; j <= b; j++)
		{
    
			if(f[i][j] == -1) continue;
			if(f[i - 1][j] == -1 && f[i][j - 1] == -1) f[i][j] = 0;
			else if(f[i - 1][j] == -1 && f[i][j - 1] != -1) f[i][j] = f[i][j - 1];
			else if(f[i - 1][j] != -1 && f[i][j - 1] == -1) f[i][j] = f[i - 1][j];
			else f[i][j] = f[i - 1][j] + f[i][j - 1];
		}
	
	
	cout << f[a][b];
}

Stack

Stack
This problem is a classic problem of Cartland number .
A stack ( infinity ) The stack sequence of is 1,2,3,…,n, How many different outbound sequences ?
answer :

h[n]=h[n−1]∗(4∗n−2)/(n+1)

Code ：

int h[N] = {1, 1};
for(int i = 2; i <= n; i++) f[i] = f[i - 1] * (4*i-2)/(i+1)

ac Code ：

#include <iostream>

using namespace std;

const int N = 20;

long long h[N];

int main()
{
    
	int n;
	cin >> n;
	h[0] = h[1] = 1;
	for(int i = 2; i <= n; i++) h[i] = h[i - 1] * (4 * i - 2) / (i + 1);
	
	cout << h[n];
}

recursive

The calculation of numbers

The calculation of numbers

Examination site ： Recursive or recursive
Write recursion first , Most of the time, recursion is to simulate the case several times , And find the rules , Get the recurrence equation .

We can find out （ It's really a little hard to find ）
notes ： This is not the only recursion , There are other rules .

 Odd hour ：f[n] = f[n - 1]
 Even number ：f[n] = f[n - 1] + f[n / 2]

ac Code

#include <iostream>

using namespace std;

const int N = 1010;

int f[N];

int main()
{
    
	int n;
	cin >> n;
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i++)
	{
    
		if(i % 2 != 0) f[i] = f[i - 1];
		else f[i] = f[i - 1] + f[i / 2];
	}
	cout << f[n];
}

recursive ：
If you start with

[1] [2] [3] [1,2] [1,3]

Then add one to the back 6 The number of solutions is

[1,6] [2,6] [3,6] [1,2,6] [1,3,6] [6]

And those sequences that started out as problem n = 1 + problem n = 2 + problem n = 3 The total number of cases of the three scales added up , On this basis, each sequence is followed by a 6( That is, the total number of cases +1） You can get the question n = 6 The answer .

---

So we can get such a formula to get the answer
The final answer = Total number of cases after downsizing + 1;

int ans = 1;
for(int i = 1; i <= n / 2; i++) ans += solution(i);

The end point of recursion is that the scale of the problem is 1 When

if(n == 1) return 1;

Code , But this way ac No. , Because there are too many repetitions .
such as sol（8） Need to call sol（2）,sol（4） Also call sol（2）, But sol（2) It's been calculated .
Therefore, it is necessary to save the previously calculated value .

#include <iostream>

using namespace std;

const int N = 1010;
int f[N];

int solution(int n)
{
    
	int ans = 1;
	if(n == 1) return 1;
	else
	{
    
		for(int i = 1; i <= n / 2; i++) ans += solution(i);
	}
	return ans;
}

int main()
{
    
	int n;
	cin >> n;
	int ans = solution(n);
	cout << ans;
}

Just take an array and save it .
Memory search ac Code

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

const int N = 1010;
int f[N];// save sol(i) Value 

int solution(int n)
{
    
	int ans = 1;
	if(f[n] != -1) return f[n];
	else
	{
    
		for(int i = 1; i <= n / 2; i++) ans += solution(i);
		f[n] = ans;
	}
	return ans;
}

int main()
{
    
	int n;
	cin >> n;
	memset(f, -1 ,sizeof(f));
	cout << solution(n);
}

function

function
This question is obviously to test your memory search .
It's simple , Open a three-dimensional array and save it all .

notes ： Because the title is bigger than 20 All return of w(20,20,20), So the array opens 25 That's enough. .

ac Code ：

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

const int N = 25;
long long f[N][N][N];

int w(int a, int b, int c)
{
    
	if(a <= 0 || b <= 0 || c <= 0) return 1;
	else if(a > 20 || b > 20 || c > 20) 
	{
    
		if(f[20][20][20] == -1) f[20][20][20] = w(20, 20, 20);
		return f[20][20][20];
	}
	else if(a < b && b < c) 
	{
    
		if(f[a][b][c - 1] == -1) f[a][b][c - 1] = w(a, b, c - 1);
		if(f[a][b - 1][c - 1] == -1) f[a][b - 1][c - 1] = w(a, b - 1, c - 1);
		if(f[a][b - 1][c] == -1) f[a][b - 1][c] = w(a, b - 1, c);
		return f[a][b][c - 1] + f[a][b - 1][c - 1] - f[a][b - 1][c];
	}
	else
	{
    
		if(f[a - 1][b][c] == -1) f[a - 1][b][c] = w(a-1,b,c);
		if(f[a - 1][b - 1][c] == -1) f[a - 1][b - 1][c] = w(a-1,b-1,c);
		if(f[a - 1][b][c - 1] == -1) f[a - 1][b][c - 1] = w(a-1,b,c-1);
		if(f[a - 1][b - 1][c - 1] == -1) f[a - 1][b - 1][c - 1] = w(a-1,b-1,c-1);
		return f[a - 1][b][c] + f[a - 1][b - 1][c] + f[a - 1][b][c - 1] - f[a - 1][b - 1][c - 1];
	}
}

int main()
{
    
	int a, b, c;
	cin >> a >> b >> c;
	memset(f, -1, sizeof(f));
	while(a != -1 || b != -1 || c != -1)
	{
    
		long long ans = w(a, b, c);
		printf("w(%d, %d, %d) = %lld\n", a, b, c, ans);
		cin >> a >> b >> c;
	}	
}

Alien code

This problem is a good study of recursion , It can be used as a classic example .

Alien code

Ideas ：
1. encounter ’[‘ Before normal reading
2. encounter ’[‘ Then read the number , Use a new string to recursively read the compressed string , Then it is spliced with the original string .
3. encounter ’]' End recursion , Returns the original string

notes ：
1. Read one character at a time
2. Recursion doesn't go deep , Just follow the above ideas

ac Code ：

#include <iostream>

using namespace std;

string expand()
{
    
	string s, X;
	char ch;
	while(cin >> ch)
	{
    
		if(ch == '[')
		{
    
			int cnt = 0;
			cin >> cnt;
			X = expand();
			for(int i = 0; i < cnt; i++) s += X;
		}
		else if(ch == ']') return s;
		else s += ch;
	}
	return s;
}

int main()
{
    
	string s = expand();
	cout << s;
}