Durham High Lord (classic DP)

The question ：

Ideas ：dfs Ideas , from 1 Start passing m Time , You can choose left or right every time , But the complexity is 2^30 Obviously not ( Can be seen as a 30 The binary number of bits , Yes 0 and 1, When traversal to 11111……111 It will traverse all the schemes , This is it. dfs Complexity ), But we can use the violence code , Write a test to see us dp Is it correct

dfs The code is as follows ：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, res;

void dfs(int u, int cnt)
{
	// Move to the left 
	if(u == 0)
	{

		dfs(n, cnt);
		return ;
	}
	if(u == n + 1)
	{
		dfs(1, cnt);
		return ;
	}
	
	if(cnt == 0)
	{
		if(u == 1)
		res ++ ;
		return ;
	}
	// Move left  
//	cout << u << endl;
	if(cnt - 1 >= 0)
	dfs(u - 1, cnt - 1); 
	// Move right 
	if(cnt - 1 >= 0) 
	dfs(u + 1, cnt - 1); 
}

int main()
{
	cin >> n >> m;
	dfs(1, m);
	
	cout << res << endl;
	return 0;
}

DP Ideas ： The equation of state of this problem is still very easy to figure out , The equation of state should grasp how to clearly describe a kind of state . Can be set f[i][j] To pass j Time , The current in i Number of schemes .

We get the equation of state transfer f[i][j] = f[i - 1][j - 1] + f[i + 1][j - 1].

You can find that the status is updated , from j - 1 Column updated . The update of the line is made by i + 1 and i - 1 to update . So if you hold it first , It will cause when calculating the current state , Their pre state has not been calculated . So here we take enumeration by column .

The code is as follows ：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5050;

int n, m, f[N][N];				//fij To pass j Time , The current in i Total number of programmes , Easy to get f[i][j] = f[i - 1][j - 1] + f[i + 1][j - 1],
								// If it is held first , It will lead to calculation fij when , The last question did not calculate , So first enumerate the columns  
int main()
{
	cin >> n >> m;
	
	f[1][0] = 1;				// Pass on 0 Time , The current in 1 Start the problem , The plan is 1
	
	for(int j = 1; j <= m; j ++ )
	for(int i = 1; i <= n; i ++ )
	{
		if(i - 1 == 0) f[i][j] = f[n][j - 1];    // A special case , Special judgement 
		else f[i][j] = f[i - 1][j - 1];
		
		if(i + 1 == n + 1) f[i][j] += f[1][j - 1];// A special case , Special judgement 
		else f[i][j] += f[i + 1][j - 1];
	}
	
	cout << f[1][m] << endl;
	return 0;
}

  In this way, we can successfully solve this problem ~~~