【算法笔记】递推方法及其例题讲解
递归与递推的区别
递归：从未知到已知 逐步接近解决问题的过程
递推：从已知到未知
递推常见内容
1.求方案数：往往需要进行乘法远离或加法原理进行累加
2.求最优值：一般没见过……
3.基础动态规划：有点难啊……
基础递推求解思路
基础递推的思考方式： 当你求第i个方案的时候，0~i-1的方案都是已知
主要的思考方式：把第i个元素加进去，对整个方案的影响
（下面会在例题中具体验证）
当然，个人还有两种非正规的解题方法：
1.暴力运行法：通过暴力运行的题目进行找规律
2.找规律：用笔演算，计算出部分小数据内容，并进行对递推式的推测
（至于证明么 …….有一个好方法：数学归纳法）
但毕竟这两种方法不一定正确，但在一定程度上使题目的解答更加容易
当然还有：动态规划求解法：根据题意设置出状态和状态转移方程，一般难度较大
取数问题
题目描述
我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。
如果你能算出一共有多少种取法，那么你会被天神Lijiganjun奖励。
输入格式
一个数n（1< n < = 50）。
输出格式
仅包含一个数——你的答案。
样例数据
input
5
output
13
数据规模与约定
时间限制：1s1s
空间限制：256MB
1.方法1:找规律
以1，2，3，4，5…n的数列为例
①n=1 有取1和不取两种
②n=2 数列1和2中：取1，取2，不取，有三种
③n=3 数列中1,2,3中：取1，取2，取3，取13，不取，有5种
④n=4 数列中1,2,3,4中：取1，取2，取3，取4，取13，取24，取14，不取，有8种
⑤n=5 由题意得，有13种
可见，当n=1-5时，ans[1-5]=2,3,5,8,13
不难发现，除了第一项和第二项，后面的每一项都是前面的两项的和，即斐波那契数列
可以得出递推式：f(i)=f(i-1)+f(i-2)
2.方法2：理解递推式的含义
设现在求的是n个数，n-1的方案数都是已知的
1.当这个数不取的时候，方案数是f(i-1)
2.当这个数取的时候，因为由题意得，数字是不能重复的，所以第n-1个数是不能选的，必然是从前n-2项的方案内容上多加一个n，故方案数是f(i-2).
综上所述，可得递推式是：f(i)=f(i-1)+f(i-2)
骨牌铺法
题目描述
有 1×n 的一个长方形，用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时为 1×3 的方格。 此时 用 1×1、1×2 和 1×3 的骨牌铺满方格，共有四种铺法。如下图：
①o o o
②o x-x
③x-x o
④x-x-x
输入格式
一个整数 n n<=40
输出格式
一个整数表示方法总数
样例数据
input
3
output
4
数据规模与约定
时间限制：1s1s
空间限制：256MB
方法1：找规律
n=0 什么都不放，1种
n=1 “o”，共1种
n=2 “o o” “x-x”，共2种
n=3 由题意得，共4种
n=4 “o o o o” “o o x-x” “o x-x-x” “x-x x-x” “x-x o o” “x-x-x o” “o x-x o” 共7种
根据数列1,1,2,4,7，可得f(i)=f(i-1)+f(i-2)+f(i-3)
方法2：暴力运行
骨牌数为1可以看成数字1，骨牌数为2可以看成数字为2，骨牌数为3可以看成数字为3
样例中
3=1+1+1 共3种方法
=2+1
=1+2
=3
同理，你可以看成是数字拆分问题，同1，2，3去拼，用DFS或完全背包运行将结果运行出来，
同样可以得到递推式：f(i)=f(i-1)+f(i-2)+f(i-3)
方法3：
我们要求的是n个位置的方案数，则已知n-1的方案数.
可以看成是由n-3，n-2，n-1的位置加上3，2，1的方块拼成的n
故递推式为：f(i)=f(i-1)+f(i-2)+f(i-3)
递推专练1：（简单数位DP）
题目描述
在所有的N位自然数（不包含0）中，有多少个数中有偶数（0也是偶数）个数字3？
输入格式
读入一个数N。1<=N<=1000。
样例数据
input
2
output
73
数据规模与约定
时间限制：1s1s
空间限制：256MB256MB
注：
0个3也是偶数个3，但是1位数里不包含0.
由于结果可能很大，你只需要输出这个答案mod 12345的值。
这就是传说中的最简单的数位DP，我们可以根据数位，数字3的个数进行求解
1.我们需要设置数组f，表示偶数个3的个数；其次，我们需要设置数组g，表示奇数个3的个数
2.我们可以得出：f[i]表示i位数字中有偶数位3的个数，g[i]表示i位数字中有奇位的个数
3.设置初始化：1-9（0不能作为个位数可忽略不计，但在数位≥2是可以使用）;f[1]=8,即没有3（0个数字3）；g[1]=3，即个位数字3.
4.动态规划过程：枚举过程十分简单，即枚举位数i，可得：f[i]=f[i-1]*9+g[i-1],表示原来有偶数个3的数字加上不是3的任何一个数字，而奇数为的数字则加上数字3；同理，g[i]=g[i-1]*9+f[i-1].
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n;
int g[10000]={0,1};
int f[10000]={0,8};
int main()
{
cin>>n;
for (int i=2;i<=n;i++)
{
f[i]=(f[i-1]*9+g[i-1])%12345;
g[i]=(g[i-1]*9+f[i-1])%12345;
}
cout<<f[n];
return 0;
} 递推专练2
题目描述
从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
输入格式
读入一个数N。1<=N<=1000。
样例数据
input
2
output
7
数据规模与约定
时间限制：1s1s
空间限制：256MB256MB
注：
由于结果可能很大，你只需要输出这个答案mod 12345的值。
显然，这道题推出正确答案的难度较大，我们可以使用暴力求解法：
我们可以使用DFS算法推算出正确答案，因为需要枚举出所有答案，所以需要使用回溯算法
这是暴力代码（还是比较简单的）
#include<bits/stdc++.h>
using namespace std;
int ans=0,n;
int vis[8000][8000]={};
void dfs(int x,int y,int step)
{
if (step==n)
{
ans++;
return;
}
if (vis[x][y+1]==0){vis[x][y+1]=1;dfs(x,y+1,step+1);vis[x][y+1]=0;}
if (vis[x][y-1]==0){vis[x][y-1]=1;dfs(x,y-1,step+1);vis[x][y-1]=0;}
if (vis[x-1][y]==0){vis[x-1][y]=1;dfs(x-1,y,step+1);vis[x-1][y]=0;}
return;
}
int main()
{
cin>>n;
vis[3000][3000]=1;
dfs(3000,3000,0);
cout<<ans;
}然后，通过暴力的达标，可以得到如下结论：
n= ans=
1 1
2 3
3 7
4 17
5 41
6 99
7 239
8 577不难得出：f(i)=f(i-1)*2+f(i-2)
所以，代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int f[1020]={1,3},n;
cin>>n;
for (int i=2;i<=n;i++)
f[i]=(f[i-1]*2+f[i-2])%12345;
cout<<f[n];
return 0;
}递推专练3
题目描述
圆周上有N个点。连接任意多条（可能是0条）不相交的弦（共用端点也算相交）共有多少种方案？
输入格式
读入一个数N。1<=N<=1000。
样例数据
input
4
output
9
数据规模与约定
时间限制：1s1s
空间限制：256MB256MB
注：
由于结果可能很大，你只需要输出这个答案mod 12345的值。
（弦：在圆周上任意两点之间的连线）
我们先来举一个简单的例子：
假设我们要求n=4，已知3.如圈1
1.若这个点什么都不连，则方案数为：f(i-1)
2.若新的点（设这个点为4号点）连接1号点，如圈2，剩下的可以连接的点的组合为：1-4的上半部分圆周和下半部分圆周.上半部分圆周有0个点，下班部分有2个点，则方案数为：f(0)+f(2)
3.若点4与点2相连，如圈3，则方案数为：f(1)+f(1)
4.若点4与点3相连，如圈4，则方案数为：f(2)+f(0)
综上所述，我们可以得到如下累加的递推式：
对于第i个点来说
如果不连弦 f[i-1]
如果连弦
和1号点连 f[0]*f[i-2] +
和2号点连 f[1]*f[i-3] +
和3号点连 f[2]*f[i-4]
...
和i-2号点连 f[i-3]*f[1]
和i-1号点连 f[i-2]*f[0]故代码实现如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
int f[10000]={1,1,2,4};
for (int i=4;i<=N;i++)
{
f[i]=f[i-1];
for (int j=1;j<=i-1;j++)
f[i]=(f[i]+f[j-1]*f[i-j-1])%12345;
}
cout<<f[N];
return 0;
}USACO:Building A Fence
题目描述
勤奋的Farmer John想给他的牛场建造一个四边形的围栏.他有一块长度为整数N (4 <= N <= 2500) 的木板.他希望在三个点上切开这块木板,把它变成长度均为整数的四块小木板.
这四块木板的长度可以是任意的正整数,只要Farmer John能够用它们组成一个四边形.那么,他有多少种不同的切割木板的方法?
注意
只要有一个切割点不同,那么两种切割方式就不同.不用考虑对称之类的复杂情况.
可以确定的是,木板的长度肯定大于0.
答案在32位整数类型可以储存的范围内.
输入格式
第1行: 一个正整数N.
输出格式
第1行: 一个正整数,表示有多少种可行的切割方式.
样例数据
input
6
output
6
Farmer John有10种切割方式: (1, 1, 1, 3), (1, 1, 2, 2), (1, 1, 3, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 3, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1) 或者 (3, 1, 1, 1). 但是 (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1) 和 (3, 1, 1, 1)四种方式不能构成四边形.
数据规模与约定
usaco Oct09。
时间限制：1s1s
空间限制：256MB
显然，我们需要直到四边形边长大小的知识才能解决问题
1.三边之和大于第四边.
2.任意一边边长大小＜周长/2
这两个条件也是下面进行动态规划的约束条件，同样也保证了结论的正确性，没有多余的解且极大地优化了时间复杂度.
先在，我们可以设置DP状态了：
1.设f[i][j]表示用了长度为i的木板且边长数为j的方案数.目标状态时：f[n][4]
2.设置状态转移方程：f[i][j]=sum(f[k][j-1])(i-longest，0≤k＜i)
状态转换方程的解释：表示从前j-1块木板中添加一块木板转移过来的，k表示前前j-1块木板的总和；longest表示每一块木板可允许存在的最大整数长度，i-longest保证了转移过来的木板都是合法的，0则保证了避免越界.
那么放代码喽：
#include<bits/stdc++.h>
using namespace std;
int f[9000][9000]={};//f[i][j]表示选用的总长度为i且已经组成了j条边的方案总数
int main()
{
int n;
cin>>n;
int longest=n/2;//s表示符合条件的边的最大长度
if (n%2==0) longest--; `
f[0][0]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=4;j++)
for (int k=max(0,i-longest);k<i;k++)
f[i][j]=f[i][j]+f[k][j-1];
cout<<f[n][4];
return 0;
} HAOI2009:
题目描述
对于一个数列{a[i]}，如果有i < j且a[i] > a[j]，那么我们称ai与aj为一对逆序对数。
若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。
那么逆序对数为k的这样自然数数列到底有多少个？
输入格式
第一行为两个整数n，k。
输出格式
一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。
样例数据
input
4 1
output
3
样例说明： 下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；
数据规模与约定
测试数据范围
30%的数据 n < = 12
100%的数据 n <= 1000，k<=1000
时间限制：1s1s
空间限制：256MB
省选题好方啊…………………
同样，我们可以选择用DP求解.
1.状态：设f[i][j]为由1-i组成的序列构成的逆序对数为j的方案总数
2.初始化：f[1][0]=1;f[2][0]=1;f[2][1]=1;
3.状态转移方程的推导与设计
先在我们已知n-1的所有内容，并需要求出n
以为之前的数列未知，我们不妨设这串数列为*******，插入的这个数为k
我们可以以此去枚举这个数字k所插入的位置(用j表示)：
1.*******k 可以看出，k比每一个数字都要大，故一串星号逆序对为：f[n-1][j]
2.******k* 可以看出，k比后面的一个数字大，一串星号构成的逆序对应该是f[n-1][j-k和后面构成的逆序对],即f[n-1][j-1]
3.*****k** 一串星号构成的逆序对为：f[n-1][j-3]
............
i-1.k******* 一串星号构成的逆序对为：f[i-1][j-(i-1)]
这样，我们就就可以得到一个状态转移方程：f[i][j]=sum(f[i-1][j-k])(0≤k≤i-1)因此，我们就可以根据上面的推导得到这道题最终的代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[2000][2000]={};//设f[i][j]为i个数逆序对数为j的方案总数
int main()
{
cin>>n>>m;
f[2][1]=f[2][0]=1;
for (int i=3;i<=n;i++)//枚举每一层数字
{
for (int j=0;j<=min(m,i*(i-1)/2);j++)//构成逆序对一共需要两个数，可根据n选2公式得数最多会产生i*(i-1)对逆序对
{
for (int k=0;k<=i-1&&k<=j;k++)//k枚举第i个数距离这个数的末尾所处的数列的位置或相当于原来的数列中前插的位置：
f[i][j]=(f[i][j]+f[i-1][j-k])%10000;
}
}
cout<<f[n][m];
return 0;
}
或许，你会对这道题产生疑问，或或许也有难理解的地方，这就是其一：
问题：例如在举例当中 ******k* 中累加的是f[i-1][j-1]而不是f[i-1][j-1]+1;可f[i][j]表示的含义不就是求的逆序对总和吗？
回答：求的是方案数，而不是逆序对的个数，一串星号的方案数是固定的，故加上k时候和后面所产生的逆序对也不会累加.
递推就写到这里啦！
希望这篇文章对读者也有所帮助，
同样也希望明天的我在考试上面也能够RP++++…….（死循环）
Bye-bye~
推荐阅读