题解 P1644 【跳马问题】
t162
2019-04-12 16:41:39
很明显的一道动态规划题目。
二维DP,$DP[i][j]$表示从起点到第$i$列第$j$行的总方案数。
根据奥数标数法(不懂可以百度)的思想,得到以下状态转移方程:
$$DP[i][j]=DP[i-1][j-2]+DP[i-1][j+2]+DP[i-2][j-1]+DP[i-2][j+1]$$
注意判断是否超出边界即可。
```cpp
#include<iostream>
using std::cin;
using std::cout;
int dp[20][20];
int main(){
int n,m;
cin>>m>>n;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==j&&j==0)dp[i][j]=1; //循环内初始化边界
else if(i==0&&j!=0)dp[i][j]=0;
else{
if(i>1){
if(j>0)dp[i][j]+=dp[i-2][j-1];
if(j!=m)dp[i][j]+=dp[i-2][j+1];
}
if(j>1)dp[i][j]+=dp[i-1][j-2];
if(j<m-1)dp[i][j]+=dp[i-1][j+2];
}
}
}
cout<<dp[n][m];
return 0;
}
```
# 分析
上述代码中的两重循环是不能交换位置的,因为题目中提到**不准往左跳**,但**并没有规定不准往上跳**,这是本题的一大坑点。如果先遍历行的话,状态转移方程就变成了这样:
$$DP[i][j]=DP[i-2][j-1]+DP[i+2][j-1]+DP[i-1][j-2]+DP[i+1][j-2]$$
($DP[i][j]$表示从起点到第$i$行第$j$列的总方案数)。
你会发现,这时候的$DP[i][j]$已经涉及到了未处理的范围,结果自然就不对了。
血的教训。