转发: 一个小公司Lucid的面经,已跪,大家请问大家面试的一道题~~~

问题是一道 longest non-repeating, non-decreasing path的题。题目是一个二位数组,求最长非降非重复路径的长度。一个数字可以向上下左右,已经对角线方向移动。
例如:
8 2 4
0 7 1
3 7 9

最长的结果为 0->2->4->7->7->9 or 1->2->4->7->7->8.

请问大家有什么好想法,谢谢!!!!


这题的变种吧,要是加上对角线的话需要再加个判断条件

真题是 +对角线, 两个元素相差大于 3, 我主要的问题是在dp 中如何保证每个元素出现一遍

感谢楼主分享!

这道题不能用DP,一个条件变了就不是DP问题了 子问题的最优解不是主问题的局部最优解

能否可請大神給我程式碼參考