G家面试题: Longest Increasing Sequence 2D matrix# JobHunting - 待字闺中
x*8
1 楼
Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
h*o
2 楼
应该也还是DP吧 上下左右比较~~
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
b*e
3 楼
先排序，然后从大往小DP。
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
j*g
4 楼
连续的么 ， 连续的好做 不连续的可能比较麻烦
x*8
5 楼
连续的，请问怎么做？
【在 j********g 的大作中提到】
: 连续的么 ， 连续的好做 不连续的可能比较麻烦
【在 j********g 的大作中提到】
: 连续的么 ， 连续的好做 不连续的可能比较麻烦
x*8
6 楼
排序？请问怎么排序？
【在 b***e 的大作中提到】
: 先排序，然后从大往小DP。
【在 b***e 的大作中提到】
: 先排序，然后从大往小DP。
b*e
7 楼
从大到小排序，记住位置。
【在 x******8 的大作中提到】
: 排序？请问怎么排序？
【在 x******8 的大作中提到】
: 排序？请问怎么排序？
x*8
8 楼
能讲下具体思路吗？
【在 h*********o 的大作中提到】
: 应该也还是DP吧 上下左右比较~~
【在 h*********o 的大作中提到】
: 应该也还是DP吧 上下左右比较~~
b*n
9 楼
recursion + memorization就行了吧，最简单直观的方法。
排序有什么太大的必要么，空间复杂度也没降。
对每个格子，看它四个方向的邻居组成的最长递增序列是多长，如果之前已经算过了就
不用再算了，如果没算过就recursion算一下
排序有什么太大的必要么，空间复杂度也没降。
对每个格子，看它四个方向的邻居组成的最长递增序列是多长，如果之前已经算过了就
不用再算了，如果没算过就recursion算一下
z*m
10 楼
http://www.careercup.com/question?id=14520685
下面的讨论里面有code和解释
下面的讨论里面有code和解释
a*m
11 楼
基本的2维dp。其实和暴力差不多。
s(x,y) = max(
if (v(x,y) > v(x-1,y)) s(x-1, y) else 1,
if (v(x,y) > v(x+1,y)) s(x+1, y) else 1,
....
)
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
s(x,y) = max(
if (v(x,y) > v(x-1,y)) s(x-1, y) else 1,
if (v(x,y) > v(x+1,y)) s(x+1, y) else 1,
....
)
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
a*m
12 楼
不用排序。dp本质上是暴力的。
【在 b***e 的大作中提到】
: 先排序，然后从大往小DP。
【在 b***e 的大作中提到】
: 先排序，然后从大往小DP。
x*8
13 楼
答案很复杂啊
【在 z***m 的大作中提到】
: http://www.careercup.com/question?id=14520685
: 下面的讨论里面有code和解释
【在 z***m 的大作中提到】
: http://www.careercup.com/question?id=14520685
: 下面的讨论里面有code和解释
相关阅读
PornHub C#面试题 (转载)湾区很多烙印开的中介给介绍的工作机会靠谱吗？想去dream company哪家公司作为跳板比较合适现在投资人都怎么这么傻逼报个 purestorage 的 offer 顺便求比较亚马逊h1身份，上周被layoff,这周拿到offer，请问该怎么办？亚麻选组请各位前辈指点问个background check的问题。如果有大公司的hr请进！尤其m家的！求助有人做过HireVue家的视频Interview么？Huami is looking for summer interns in mobile/wearable computing华米USA(小米手环)招Full Time Senior Backend Engineer求问2个小公司：Machine Zone and Springpath.烙印媒体成名青云直上的妙计 (转载)面试google面试的郁闷有人对Bloomberg家dev了解么？ (转载)请教如何和说话不靠谱的HR打交道？"这"内推脸书黑人生命重要事件看工作AA (转载)求oculus内推background check要走国内的身份证号进行犯罪调查