Mr Loser

题解 P1644 【跳马问题】

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]$$

注意判断是否超出边界即可。

#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]$ 已经涉及到了未处理的范围,结果自然就不对了。

血的教训。