作者FrankTrjpp (请给我前叉)
看板C_and_CPP
标题[问题] 路径点数问题
时间Mon Jun 8 05:14:13 2009
期末考的考题
一直想不通到底错在哪边
┌─┬─┐ 一个表格如右，假设他可用座标来表达位置
│ 3│ 4│ 例如 1在(0,0)的点，2在(0,1)
├─┼─┤
│ 1│ 2│ n*n的正方形表格，表格内的数字为分数(score)
└─┴─┘
只能往右、上、右上走，有负数情况
题目问，走过哪一条路径，可以使得经过的分数总和为最高，输出最高分数极可
比如此表格
↑→的分数是1+3+4=8
↗ 的分数是 1+4 =5
→↑的分数是1+2+4=7
因此我们知道最大分数是8
我的做法是
当x为零(1 3这排)，则各点总分可直接加算 (0,0)这点分数是1， (1,0)是1+3=4
当y为零(1 2这排)，则各点总分可直接加算 (0,0) 1 (0,1) 1+2=3
当x>0&&y>0(4这排)，各点总分 考虑该点左方、左下方、下方三点分数
将最大者与自身相加 (4比3、1大，所以挑左边的4加上本身分数4=8)
请问这样有什麽问题?
我觉得我只是把递回从(0,0)开始写，然後用while跑递回
小测资答案是对的，大测资是错的
我想知道为什麽会错(诡论?)
感谢~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.227.195.24
1F：推 yauhh:因为你用贪婪的算法处理,顾不到全局中最大值的路径, 06/08 06:20
2F：→ yauhh:你舍弃的区域小路径仍有可能带往全局的大路径 06/08 06:21
3F：推 littleshan:这是典型用 DP 解的问题 06/08 08:10
4F：推 ledia:更新的顺序? 简单解释一下你的演算法吧 ? 06/08 11:19
5F：→ ledia:DP 即可, 不用去考虑什麽全局、区域的搜寻考量 06/08 11:20
6F：推 Yshuan:graph 自己建图 最後跑最"长"路径... 06/08 12:23
7F：→ FrankTrjpp:可以举个反例吗@@ 如果方法是错的至少有1反例吧 06/09 05:42
8F：→ netsphere:那就是递回写错拉 06/09 19:19