(相关资料图)
原题链接
这是一道经典的动态规划题目。
如果尝试使用深度优先搜索（dfs）或广度优先搜索（bfs）做就会获得 TLE （注意数据范围）。于是我们想到了更为高级的动态规划（Dynamic Programming, dp）。
简略介绍动态规划算法的核心思想：把原问题分解为相对简单的子问题的方式求解复杂问题。与递推有几分相似？递推其实是动态规划的一个分支！
在求解动态规划这一类问题时，一般有三步：
在这道题目中，可以使用一个二维数组 dp[n][m] 来存放每一个子问题的答案，即用 dp[i][j] 来表示到达第i行第j列所需的最多步数，dp[n][m] 也就是答案了。
由于过河卒初始就在第0列第0行，所以 dp[0][0] = 1；而他只能向下走或向右走，当在第0行或第0列时，情况只有1种。
动态规划一类题目中的最关键部分。过河卒只能向下走或向右走，故 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
注意：还要注意马可以到达的地方，过河卒不能到达。
1 #include2 using namespace std; 3 const int N = 25; 4 const int dir[][2] = { 5 {1, 2}, {1, -2}, {2, 1}, {2, -1}, 6 {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1} 7 }; 8 long long dp[N][N]; 9 int n, m, sx, sy;10 bool vis[N][N];11 int main() {12 cin >> n >> m >> sx >> sy;13 vis[sx][sy] = true;14 for (int i = 0; i < 8; i ++){15 int tx = sx + dir[i][0];16 int ty = sy + dir[i][1];17 if (tx >= 0 && tx <= n && ty >= 0 && ty <= m)18 vis[tx][ty] = true;19 }20 dp[0][0] = 1;21 for (int i = 0; i <= n; i ++)22 for (int j = 0; j <= m; j ++)23 if (!vis[i][j]){24 if (i) dp[i][j] += dp[i - 1][j];25 if (j) dp[i][j] += dp[i][j - 1];26 }27 cout << dp[n][m];28 return 0;29 }
关键词：
新闻发布平台 |科极网 |环球周刊网 |tp钱包官网下载 |中国创投网 |教体产业网 |中国商界网 |万能百科 |薄荷网 |资讯_时尚网 |连州财经网 |剧情啦 |5元服装包邮 |中华网河南 |网购省钱平台 |海淘返利 |太平洋装修网 |励普网校 |九十三度白茶网 |商标注册 |专利申请 |启哈号 |速挖投诉平台 |深度财经网 |深圳热线 |财报网 |财报网 |财报网 |咕噜财经 |太原热线 |电路维修 |防水补漏 |水管维修 |墙面翻修 |旧房维修 |参考经济网 |中原网视台 |财经产业网 |全球经济网 |消费导报网 |外贸网 |重播网 |国际财经网 |星岛中文网 |手机测评 |品牌推广 |名律网 |项目大全 |整形资讯 |整形新闻 |美丽网 |佳人网 |税法网 |法务网 |法律服务 |法律咨询 |成报网 |媒体采购网 |聚焦网 |参考网
中国资本网 版权所有
Copyright © 2011-2020 亚洲资本网 All Rights Reserved. 联系网站：55 16 53 8 @qq.com
