后续【算法1-4】递推与递归这个题单下做的题都更新到这。
汇总一下题单里自己做过的题目,也算是复习消化一下dp思想了。
题单名称
【算法1-4】递推与递归
P1002 [NOIP2002 普及组] 过河卒
题目描述
棋盘上 A A A 点有一个过河卒,需要走到目标 B B B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C C C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示, A A A 点 ( 0 , 0 ) (0, 0) (0,0)、 B B B 点 ( n , m ) (n, m) (n,m),同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A A A 点能够到达 B B B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示 B B B 点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
样例 #1
样例输入 #1
6 6 3 3
样例输出 #1
6
提示
对于 100 % 100 \% 100% 的数据, 1 ≤ n , m ≤ 20 1 \le n, m \le 20 1≤n,m≤20, 0 ≤ 0 \le 0≤ 马的坐标 ≤ 20 \le 20 ≤20。
【题目来源】
NOIP 2002 普及组第四题
思路
后续看别人题解的时候才发现原来根本就不需要考虑马的控制点是否会越界,因为数据给的都是不越界的。
原先是用dfs做的,不断的往右和往下深搜,最后TLE了,然后改成dp了。
经典的dp题。思路也很简单:
因为卒只能往x和y增长的方向前进,因此每一个位置都只可能是由x和y减少的方向而走来的
那么我们设一个二维数组dp[i][j],i和j分别代表坐标值,dp[i][j]就是由原点走到i,j点的路径数量
到这里状态转移方程就出来了
dp[i][j] = dp[i-1][j] + dp[i][j-1];
设置边界条件,dp[0][0] = 1
然后就可以递推了。
代码
// P1002 [NOIP2002 普及组] 过河卒
// dp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,mn,mm;
int pos[30][30] = {0};
ll dp[30][30] = {0};
bool gud(int x, int y){
//判断坐标为x,y的点是否在范围内
if(x<=n && x>=1 && y <=m && y>=1)
return true;
else return false;
}
int main(){
cin >> n >> m >> mn >> mm;
n++;
m++;
mn++;
mm++;
//将马的控制点设为1
pos[mn][mm] = 1;
if(gud(mn-2,mm+1)) pos[mn-2][mm+1] = 1;
if(gud(mn-2,mm-1)) pos[mn-2][mm-1] = 1;
if(gud(mn-1,mm+2)) pos[mn-1][mm+2] = 1;
if(gud(mn-1,mm-2)) pos[mn-1][mm-2] = 1;
if(gud(mn+2,mm+1)) pos[mn+2][mm+1] = 1;
if(gud(mn+2,mm-1)) pos[mn+2][mm-1] = 1;
if(gud(mn+1,mm+2)) pos[mn+1][mm+2] = 1;
if(gud(mn+1,mm-2)) pos[mn+1][mm-2] = 1;
//开始dp
dp[1][1] = 1;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(i==1 && j==1) continue;//dp[1][1]已经被初始化,不能被改
if(!pos[i][j]){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
cout << dp[n][m];
return 0;
}
P1044 [NOIP2003 普及组] 栈
题目背景
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。
题目描述
宁宁考虑的是这样一个问题:一个操作数序列, 1 , 2 , … , n 1,2,\ldots ,n 1,2,…,n(图示为 1 到 3 的情况),栈 A 的深度大于 n n n。
现在可以进行两种操作,
- 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
- 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3
生成序列 2 3 1
的过程。
(原始状态如上图所示)
你的程序将对给定的 n n n,计算并输出由操作数序列 1 , 2 , … , n 1,2,\ldots,n 1,2,…,n 经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数 n n n( 1 ≤ n ≤ 18 1 \leq n \leq 18 1≤n≤18)。
输出格式
输出文件只有一行,即可能输出序列的总数目。
样例 #1
样例输入 #1
3
样例输出 #1
5
提示
【题目来源】
NOIP 2003 普及组第三题
思路
dp数组中i代表栈内元素,j代表待进栈的元素(注意已经出栈的元素不能再退栈
那么我们很自然的就想到,当j = 0 的时候情况为1,这就是边界条件dp[i][0] = 1 情况唯一,依次出栈
那么状态转移的过程就是压栈和出栈,写成方程就是
dp[i][j] = dp[i+1][j-1] + dp[i-1][j]
这里要注意,i=0时只能压栈不能出栈,因为i=0的时候代表栈空,此时方程要改为
dp[0][j] = dp[1][j-1]
到此分析结束
代码
// P1044 [NOIP2003 普及组] 栈
// dp[i][j] = dp[i+1][j-1] + dp[i-1][j] 压栈 + 出栈
// dp[i][0] = 1 情况唯一,依次出栈
// dp[0][j] = dp[1][j-1] 压栈
#include <bits/stdc++.h>
using namespace std;
int main(){
int dp[20][20] = {0};
int n;
cin >> n;
for(int j=0; j<=n; j++){
for(int i=0; i<=n; i++){
// 这里需要解释为什么先枚举j后枚举i
// 因为dp的状态要根据上一个状态而来
// 原本dp数组都是0,0是初始化的状态不能直接被引用
// 下面三个情况里,只看第一个和第二个两个状态转移的情况
// 将dp数组视作矩阵,那么(i,j)坐标都依靠左下(i+1,j+1)和上(i-1,j)这两个状态
// 因此我们要以列序优先,保证左下能够满足必定是更新过的状态,而不是初始化值
if(j==0) dp[i][j] = 1;
else if(i>=1) dp[i][j] = dp[i+1][j-1] + dp[i-1][j];
else dp[i][j] = dp[i+1][j-1];
}
}
cout << dp[0][n];
return 0;
}
P1028 [NOIP2001 普及组] 数的计算
题目描述
我们要求找出具有下列性质数的个数(包含输入的正整数 n n n)。
先输入一个正整数 n n n( n ≤ 1000 n \le 1000 n≤1000),然后对此正整数按照如下方法进行处理:
不作任何处理;
在它的左边拼接一个正整数,但该正整数不能超过原数,或者是上一个被拼接的数的一半;
加上数后,继续按此规则进行处理,直到不能再加正整数为止。
输入格式
一行,一个正整数 n n n( n ≤ 1000 n \le 1000 n≤1000)。
输出格式
一个整数,表示具有该性质数的个数。
样例 #1
样例输入 #1
6
样例输出 #1
6
提示
【样例解释】
满足条件的数为: 6 6 6, 16 16 16, 26 26 26, 126 126 126, 36 36 36, 136 136 136。
【题目来源】
NOIP 2001 普及组第一题
思路
这题是看了题解才做出来的,真的巧妙
递推式在代码注释里,思想很简单
设一维数组f[i],代表n=i的情况数
就是利用前面数字的情况之和,也就是前缀和,再加上已有数字就构成了我们需要求的数字,注意还需要再加上单数字n的一种情况,就构成了f[n]
递推式为f[i] = f[1] + f[2] + … + f[i/2]
代码
// P1028 [NOIP2001 普及组] 数的计算
// f[i]表示n=i的情况数
// 可以得到递推式,就是f[i] = f[1] + f[2] + ... + f[i/2]
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
int n;
cin >> n;
int *f = new int[1010]();
// f[0] = 0;
// f[1] = 1;
// int f[1010] = {0,1};
for(int i=2; i<=1000; i++){
for(int j=1; j<=i/2; j++)
f[i] += f[j];
f[i]++;
}
cout << f[n];
return 0;
}
P1464 Function
题目描述
对于一个递归函数 w ( a , b , c ) w(a,b,c) w(a,b,c)
- 如果 a ≤ 0 a \le 0 a≤0 或 b ≤ 0 b \le 0 b≤0 或 c ≤ 0 c \le 0 c≤0 就返回值$ 1$。
- 如果 a > 20 a>20 a>20 或 b > 20 b>20 b>20 或 c > 20 c>20 c>20 就返回 w ( 20 , 20 , 20 ) w(20,20,20) w(20,20,20)
- 如果 a < b a<b a<b 并且 b < c b<c b<c 就返回$ w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$。
- 其它的情况就返回 w ( a − 1 , b , c ) + w ( a − 1 , b − 1 , c ) + w ( a − 1 , b , c − 1 ) − w ( a − 1 , b − 1 , c − 1 ) w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1) w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)
这是个简单的递归函数,但实现起来可能会有些问题。当 a , b , c a,b,c a,b,c 均为 15 15 15 时,调用的次数将非常的多。你要想个办法才行。
注意:例如 w ( 30 , − 1 , 0 ) w(30,-1,0) w(30,−1,0) 又满足条件 1 1 1 又满足条件 2 2 2,请按照最上面的条件来算,答案为 1 1 1。
输入格式
会有若干行。
并以 − 1 , − 1 , − 1 -1,-1,-1 −1,−1,−1 结束。
保证输入的数在 [ − 9223372036854775808 , 9223372036854775807 ] [-9223372036854775808,9223372036854775807] [−9223372036854775808,9223372036854775807] 之间,并且是整数。
输出格式
输出若干行,每一行格式:
w(a, b, c) = ans
注意空格。
样例 #1
样例输入 #1
1 1 1
2 2 2
-1 -1 -1
样例输出 #1
w(1, 1, 1) = 2
w(2, 2, 2) = 4
思路
记忆化搜索
直接计算会TLE
所以要先记录下每一个情况的值,然后直接读取数组的值并输出就可以大大节约时间,不必每次打印都计算一遍。
这个过程中的核心是要保存计算过的数组值,在下次计算时遇到计算过的值直接调用即可。
代码
// P1464 Function
// 记忆化搜索
#include<iostream>
using namespace std;
typedef long long ll;
long w[21][21][21] = {1};//记忆化全局变量
ll fw(ll a,ll b, ll c){
//核心代码,返回过程中要赋值给全局变量
if(a<=0 || b<=0 || c<=0){
return 1;
} else if(a>20 || b>20 || c>20){
return fw(20,20,20);
} else if(w[a][b][c])
//记忆化搜索核心代码
return w[a][b][c];
else if(a<b && b<c)
w[a][b][c] = fw(a,b,c-1) + fw(a,b-1,c-1) - fw(a,b-1,c);
else
w[a][b][c] = fw(a-1,b,c) + fw(a-1,b-1,c) + fw(a-1,b,c-1) - fw(a-1,b-1,c-1);
return w[a][b][c];
}
int main(){
int a, b, c;
cin >> a >> b >> c;
while(a!=-1 || b!=-1 || c!=-1){
cout <<"w(" << a << ", " << b << ", " << c << ") = " << fw(a,b,c) << endl;
cin >> a >> b >> c;
}
return 0;
}