算法——Coin-collecting by robot

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法——Coin-collecting by robot，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1478字，纯文字阅读大概需要3分钟。

内容图文

题目描述

Several coins are placed in cells of an n×m board. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location.

输入

The fist line is n,m, which 1< = n,m <= 1000.
Then, have n row and m col, which has a coin in cell, the cell number is 1, otherwise is 0.

输出

The max number Coin-collecting by robot.

样例输入

5 6
0 0 0 0 1 0
0 1 0 1 0 0
0 0 0 1 0 1
0 0 1 0 0 1
1 0 0 0 1 0

样例输出

5

代码

#include<iostream>
using namespace std;
int Coor[1000][1000];
int main(){
	int N, M;
	cin>>N>>M;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			cin>>Coor[i][j];
			if(i == 1 && j > 1) Coor[1][j] += Coor[1][j-1];
			if(j == 1 && i > 1) Coor[i][1] += Coor[i-1][1];
			if(i > 1 && j > 1) Coor[i][j] += max(Coor[i][j-1],Coor[i-1][j]);
		}
	}  
	cout<<Coor[N][M]<<endl;
	return 0;
}

思路

1. 动态规划问题；

2. 令F( i , j )为机器人截止到第 i 行第 j 列单元格 ( i , j ) 能够收集到的最大硬币数, 有如下递推式：
   

3. 值得注意的是：递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

4. 我第一次用了递归的方式，出现了 Time Limit Exceeded ,普通循环修正以后，便可以通过。

5. 但可以 利用上面的公式，我们可以通过逐行或者逐列的方式填充 n 乘以 m 表以求得F( i , j )。

内容总结

以上是互联网集市为您收集整理的算法——Coin-collecting by robot全部内容，希望文章能够帮你解决算法——Coin-collecting by robot所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---