蓝桥杯 算法训练 N车问题 c++解法

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　给定N×N的棋盘，问有多少种放置N个车使他们不互相攻击的方案。

输入格式

　　一行一个整数，N。

输出格式

　　一行一个整数，表示方案数。

样例输入

3

样例输出

6

数据规模和约定

　　N<=20

---

一开始用dfs（深度搜素），最后会因为运行超时，所以参考了其他人对于这道题目的解法，知道了要用动态规划的方法，注意存储结果的数组应该用long long数据类型，这不然到N=20时会由于数据过大而溢出（搜了挺多资料，发现并没有对于这道题目的C++解法，所以决定写下我的解题过程，希望能够帮助到大家！！）

参考文章链接：链接

#include<bits/stdc++.h>
using namespace std;


int main()
{
	int n;
	cin >> n;
	long long dp[21]={0};
	dp[1]=1;
	for(int i=2;i<=n;i++)
	{
		dp[i]=dp[i-1]*i;
	}
	cout << dp[n] << endl; 
	return 0;
}