题解 P1644 【跳马问题】

t162 · 2019-04-12 16:41:39 · 题解

很明显的一道动态规划题目。

二维DP，DP[i][j]表示从起点到第i列第j行的总方案数。

根据奥数标数法(不懂可以百度)的思想，得到以下状态转移方程：

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

#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]表示从起点到第i行第j列的总方案数)。

你会发现，这时候的DP[i][j]已经涉及到了未处理的范围，结果自然就不对了。

血的教训。