欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷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;
}

 

相关标签: oj