题解 P1644 【跳马问题】

t162

2019-04-12 16:41:39

Solution

很明显的一道动态规划题目。 二维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]$已经涉及到了未处理的范围,结果自然就不对了。 血的教训。