-- 发布时间：11/28/2006 1:25:00 PM
-- [求助]机器人拾硬币
A checkerboard has a certain number of coins on it
A robot starts in the upper-left corner, and walks to the bottom left-hand corner
The robot can only move in two directions: right and down
The robot collects coins as it goes
You want to collect all the coins using the minimum number of robots
Example:
Do you see a greedy algorithm for doing this?
Does the algorithm guarantee an optimal solution?
Can you prove it?
Can you find a counterexample?
简单的说：
机器人从如图所示的位置出发，值能向右和向下行走，不能后退和上走，问如何才能用最少的机器人捡完所有的硬币。N*N。所以需要一个N平方级别的时间复杂度。不能用递归算。
谁能给个好的算法，多谢了