洛谷P1002 过河卒--优化递归与动态规划的AC解法
程序员文章站
2022-04-01 17:26:48
...
题目链接:https://www.luogu.org/problemnew/shouw/Pi1002
思路
由于卒子只能向两个方向走,所以卒子到达一个点的方法数等于到达这个点左1的方法数+到达这个点上1的方法数,即状态转移方程为dp[i][j]={dp[i-1][j]+dp[i][j-1]},明白了这个,我们可以用递归和非递归(也就是动态规划)来解题
1.优化递归解法
这是我非常倡导的一种解法,我们用递归无疑会超时,但是要明白超时是因为做了大量重复的计算,而我们如果定义一个数组,每次将得到的结果存至数组中,下次进行递归时先判断,如果数组中有数据就从数组中取数,而如果数组中没数据再递归,这样就省去了重复计算,而思路又是递归的思路,所以很好写。
AC代码:
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXV=21;
ll kind[MAXV][MAXV];
ll n,m,hx,hy;
bool judgeHor(ll x,ll y){
if((x==hx+2 && y==hy+1) || (x==hx+2 && y==hy-1)
|| (x==hx-2 && y==hy+1) || (x==hx-2 && y==hy-1)
|| (x==hx+1 && y==hy+2) || (x==hx+1 && y==hy-2)
|| (x==hx-1 && y==hy+2) || (x==hx-1 && y==hy-2)
|| (x==hx && y==hy)){
return false;
}else return true;
}
ll getGoal(ll x,ll y){
if(x<0 || y<0) return 0;
if(x==0 && y==0) return 1;
if(judgeHor(x,y)){
if(kind[x][y]!=0){ //关键的一步
return kind[x][y];
}
ll rel=getGoal(x-1,y)+getGoal(x,y-1);
kind[x][y]=rel;
return rel;
}else {
return 0;
}
}
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&hx,&hy);
fill(kind[0],kind[0]+MAXV*MAXV,0);
printf("%lld\n",getGoal(n,m));
return 0;
}
2.动态规划解法
动态规划就是直接利用上面的状态转移方程了,非常好写。
AC代码:
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXV=21;
ll dp[MAXV][MAXV];
ll n,m,hx,hy;
bool judgeHor(ll x,ll y){
if((x==hx+2 && y==hy+1) || (x==hx+2 && y==hy-1)
|| (x==hx-2 && y==hy+1) || (x==hx-2 && y==hy-1)
|| (x==hx+1 && y==hy+2) || (x==hx+1 && y==hy-2)
|| (x==hx-1 && y==hy+2) || (x==hx-1 && y==hy-2)
|| (x==hx && y==hy)){
return false;
}else return true;
}
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&hx,&hy);
fill(dp[0],dp[0]+MAXV*MAXV,0);
dp[0][0]=1;
for(int i=0;i<MAXV;i++){
for(int j=0;j<MAXV;j++){
if(!judgeHor(i,j)) continue;
if(i>=1){
dp[i][j]+=dp[i-1][j];
}
if(j>=1){
dp[i][j]+=dp[i][j-1];
}
if(i==n && j==m){
printf("%lld\n",dp[i][j]);
break;
}
}
}
return 0;
}