前情见半年前的《为什么我总写不出递推》
emmm之前还说什么一看题解就会，现在是看了题解就知道考场上打死也想不出来（还有开long long !!!）
- 把问题分层，分成无数的子问题
- 根据递归 递推的定义，问题应具有子母问题解决方案一致的性质
- 找出第n想与他的前几项之间的关系，就是递推式（打表找规律不是盖的）
T1：错排
对于1~n的乱序序列，有多少情况 a i != i
由题意a1=0，a2=1，当n≥3时，在错排中n必不在第n位，设n放在第k位上（1≤k≤n-1），则第n位上有两种可能：
（1）如果第n位上不是k，那么把第n位看作第k位，将n以外的n－1个数进行错排，错排个数是an-1；
（2）如果第n位上是k，那么除n和k以外的n－2个数的错排是an-2，
所以n在第k位上的错排数共有an-1＋an-2，由于k可取1、2、3、4、……、n－1共n－1种取法
查看代码
long long work(int n)
{
if (n == 0 || n == 1) return 0;
else if (n == 2) return 1;
else return (n-1) * (work(n-2) + work(n-1));
}T2：数的划分
把 n 分为可重复的 k 个数（13 31算一种情况），有多少方法
f[i][j]指把数 i 分解成 j 份
因为分解的每一份不能为空，则先将每一份都分配 1，剩余数值为 i-j ，再将 i-j 分为 1 份，2份，...，j份。
即 f[i][j] = f[i-j][1]+f[i-j][2]+...+f[i-j][j]
又 f[i-1][j-1] = f[i-j][1]+f[i-j][2]+...+f[i-j][j-1]
可得 f[i][j]=f[i-j][j]+f[i-1][j-1]
查看正常代码
int main()
{
int n,k,f[2050][2050];
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
if(i==j) f[i][j]=1;
else if(i<j) f[i][j]=0;
else if(i>j) f[i][j]=f[i-1][j-1]+f[i-j][j];
}
}
printf("%d",f[n][k]);
return 0;
}查看我的代码
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) f[i][1]=1;
for(int i=2;i<=k;i++){
f[i][i]=1;
for(int j=i+1;j<=n;j++) f[j][i]+=f[j-1][i-1]+f[j-i][i];
}
printf("%d", f[n][k]);
return 0;
}整理此题时我惊奇地发现我的做法和网上（几乎）所有代码都不一样，把 i j 调过来。但是加或不加都能 AC。这使我突然意识到一个问题：不是所有递推式都会经过不断的累加，还有很多是单次赋值就行的，以及全局变量的优越性
T3：传球游戏
源问题：从1号位置开始传球,第m步球回到1号位置的方法数
子问题：从1号位置开始传球,第 i 步球传到 j 号位置的方法数
dp[i][j] ：表示第 i 次传球之后,球在第 j 个人手上的方法数
确定状态转移方程
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
当前状态 = 上一状态从左边传过来的方法数 + 上一状态从右边传过来的方法数
注意成环需要考虑边界左边右边的人的编号
最后dp[m][1]就表示传球m次 , 球回到1号位置的方法数
查看代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int dp[40][40]={0};
int n,m;
cin>>n>>m;
dp[0][1]=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int a=j-1;
if(a==0) a=n;
int b=j+1;
if(b==n+1) b=1;
dp[i][j]=dp[i-1][a]+dp[i-1][b];
}
}
cout<<dp[m][1]<<endl;
return 0;
}T4：栈的问题
一个操作数序列，1,2,3，....，n，保证不会爆栈
现在可以进行两种操作：
- 将一个数，从操作数序列的头端移到栈的头端
- 将一个数，从栈的头端移到输出序列的尾端
计算由操作数序列 经过操作可能得到的输出序列的总数。
这个问题可以化为构造二叉树：对于有 n 个节点的二叉树，可以构造出多少形态，详见为什么我总写不出递推
查看代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
long long f[10010];
cin>>n;
f[0]=1;
f[1]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<i;j++)
f[i]=f[i]+f[i-j-1]*f[j];
cout<<f[n];
return 0;
}