很久只前我有个朋友提出一道某大公司应聘的题目，今晚突然回想起来，觉得很有趣
如下
有一个 m * n 的矩阵，m n 是提供的确定的数，但算法必须适应任意情况。
里面的数是不确定（任意的）的，要求按一定的方向（如图），
从左上角第一个元素走到右下角最后一个元素，只能向右和向下走，每走一步，加上那
个数，要求得到的数最小。
要求如下：
第一：算法要简单
第二：效率要高（因为数据可能很多）
比如：
1 8 0
7 8 8
7 15 1
那么最优路径就是
1 8 0
8
1
下面我提出自己的想法：
首先：遍历整个矩阵（二维数组），得到最大的那个数，用一个标记替换他如 '#' ，重复这一，
大概 n 次（n为可能路径 (还在计算中，会补上的) 的1/3）；
然后：用循环，判断（排除前面的标记）得到剩下路径，取出最优值；（如果剩下的个数
还很大，可以重复上一步操作）
这个我的自己的想法，不知道您有没有其他的想法？请多多指教！
如果您知道，可能的路径数目的计算公式，也希望你能提供我参考；谢谢！！！
地震让大伙知道：居安思危，才是生存之道。
posted on 2007-09-03 22:35
小寻 阅读(2206)
评论(11) 编辑 收藏 所属分类:
算法