备战蓝桥杯---动态规划（基础1）

先看几道比较简单的题：

直接f[i][j]=f[i-1][j]+f[i][j-1]即可（注意有马的地方赋值为0）

下面是递推循环方式实现的AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
signed main(){cin>>n>>m>>x>>y;x++;y++;m++;n++;a[1][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if((abs(x-i)==1&&abs(y-j)==2)||(abs(x-i)==2&&abs(y-j)==1)||(x==i&&y==j)){a[i][j]=0;continue;}if(i==1&&j==1) continue;a[i][j]=a[i][j-1]+a[i-1][j];}}cout<<a[n][m];
}

下面是记忆化数组实现的AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
int dir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
int dp(int x,int y){if(x<=0||x>n||y>m||y<=0) return 0;if(a[x][y]!=-1) return a[x][y];return a[x][y]=dp(x-1,y)+dp(x,y-1);
}
signed main(){cin>>n>>m>>x>>y;x++;y++;n++;m++;memset(a,-1,sizeof(a));a[1][1]=1;a[x][y]=0;for(int i=0;i<8;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx<=0||xx>n||yy>m||yy<=0) continue;a[xx][yy]=0;}cout<<dp(n,m);
}

接题：

我们定义f[i][j]为第j同学的方案数（注意n位同学旁边为1号与n-1)

下面是递推循环方式实现的AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int dp[40][40];
signed main(){cin>>n>>m;dp[1][0]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(j==1){dp[j][i]=dp[n][i-1]+dp[j+1][i-1];}else if(j==n){dp[j][i]=dp[j-1][i-1]+dp[1][i-1];}else{dp[j][i]=dp[j-1][i-1]+dp[j+1][i-1];}}}cout<<dp[1][m];
}

下面是用记忆化搜索的实现代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int dp[40][40];
int f(int x,int y){if(y<0) return 0;if(dp[x][y]!=-1) return dp[x][y];if(x==1) return dp[x][y]=f(n,y-1)+f(x+1,y-1);if(x==n) return dp[x][y]=f(x-1,y-1)+f(1,y-1);return dp[x][y]=f(x-1,y-1)+f(x+1,y-1);
}
signed main(){cin>>n>>m;memset(dp,-1,sizeof(dp));dp[1][0]=1;for(int i=2;i<=n;i++) dp[i][0]=0;cout<<f(1,m);
}

注意，在用记忆化搜索时，memset语句是必要的，如果不加，那么dp[x][y]!=0时返回，但事实上，我们有很多地方值为0，意味这退出情况大多是y<0在起作用，因此，记忆化的作用发挥不出来，虽然答案对，但是运行很慢。