题目背景
在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……
题目描述
中国象棋半张棋盘如图 1所示。马自左下角 (0,0)向右上角 (m,n) 跳。规定只能往右跳，不准往左跳。比如图 1 中所示为一种跳行路线，并将路径总数打印出来。
输入格式
只有一行：两个数 n，m。
输出格式
只有一个数：总方案数 total。
输入输出样例
输入 #1
4 8输出 #1
37说明/提示
对于 100% 的数据：n,m≤18
我的思路
此题乍一看就是深搜，不过小编认为dp法更简单。题目中说，马不能向左走，所以我们只需考虑四个方向的情况。
x[4] = {1, 2, 2, 1}, y[4] = {2, 1, -1, -2}得出dp公式： dp[i][j] = dp[i - 1][j - 2] + dp[i - 2][j - 1] + dp[i - 2][j + 1] + dp[i - 1][j + 2]
至于第一个for为什么从1开始，是因为从（0,0）出发， 因为马只能往右边走，所以i = 0时，没有任何情况经过，至少从i= 1开始。
AC代码
#include<bits/stdc++.h> using namespace std; int n, m, dp[21][21], x[4] = {1, 2, 2, 1}, y[4] = {2, 1, -1, -2}; int main() { cin >> n >> m; dp[0][0] = 1; for (int i = 1; i <= m; i++) for (int j = 0; j <= n; j++) for (int k = 0; k <= 3; k++) if (i - x[k] >= 0 && j - y[k] >= 0) dp[i][j] += dp[i - x[k]][j - y[k]]; cout << dp[m][n]; return 0; }