擅长排列的小明 II
- 描述
-
小明十分聪明，而且十分擅长排列计算。
有一天小明心血来潮想考考你，他给了你一个正整数n，序列1,2,3,4,5......n满足以下情况的排列：
1、第一个数必须是1
2、相邻两个数之差不大于2
你的任务是给出排列的种数。
- 输入
- 多组数据。每组数据中输入一个正整数n（n<=55）.
- 输出
- 输出种数。
- 样例输入
-
4
- 样例输出
-
4
用深搜也能得出答案，但是，，超时。。。。
神搜代码：#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;int n,sum;
bool flag[60];//判断1~n这些数是否使用过；
void DFS(int count,int m)
{
if(count==n)
{
sum++;
return ;
}
for(int i=1;i<=n;i++)
if((!flag[i])&&(fabs(i-m)<=2))//因为后面数可能比前面的数小，所以用fabs
{
flag[i]=true;
DFS(count+1,i);
flag[i]=false;
}
}int main()
{
while(cin>>n)
{
sum=0;
memset(flag,false,sizeof(flag));//全致为false（没使用过）
flag[1]=true;//1肯定使用过，因为第一个只能为1
DFS(1,1);//两个形参的含义：要判断的数的个数（计数作用，从一个数开始）和当前的数字是什么（从1开始）
cout<<sum<<endl;
}
return 0;
}dp：
#include <iostream>
#include <cstring>
using namespace std;int main()
{
int n;
while(cin>>n)
{
int dp[60];
memset(dp,0,sizeof(dp));
dp[0]=0;
dp[1]=1;
dp[2]=1;
for(int i=3;i<=55;i++)
dp[i]=dp[i-1]+dp[i-3]+1;
cout<<dp[n]<<endl;
}
return 0;
}/* 思路：
dp[i] 表示数字为i时的排列方法的总数；
首位必须为1，当第二位的数字等于2时：相当于给2~n个数排列（1~n-1）
当第二位的数字等于3时：
第三位可能为4 5 2
当第三位为4时，无论第四位取不取2都不满足题意（1 3 4 2 5 不满足||1 3 4 5 2 不满足）。
当第三位为2时，第四位为4，相当于求4~n的排列（1~n-3）。
当第三位为5时，1 3 5 7 9 ...2*n+1 2*n ... 6 4 2 只有这一种情况。
所以,dp[0]=0,dp[1]=dp[2]=1,dp[3]的情况等于dp[2]的情况+dp[0]的情况+1
...以此类推。
*/