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和解释
相关阅读
本版的两个傻逼习惯你永远都捉摸不透的事情（转载）看到有些公司招remote职位求大神说说如何设计一个ecommerce的reservation system两个工作之间有半个月的gap可以吗algorithm完全忘光了，做leetcode之前是不是要把Introduction_to_Algorithms_3rd_Edition看一遍？Flipbroad现在怎么样了？对社会的残疾人不应该有“双重标准”？长期内推box机器学习是hype还是真的缺人？其它公司找我，什么时候告诉现在的employer比较好？医学物理，地球物理or cs? (转载)H1B Transfer 算是 Sponsorship 吗？能力普通的码工应该何去何从 (转载)H1b开始后 OPT是否自动失效？也就是说必须在H1b开始日开始工作？H1B和PIP的问题求建议LinkedIn onsite一道题淘宝上低价代理下载amazon kindle书是怎么实现的那个BSO的Jennifer85 说说, 你们两口子做什么工作的 (转载)Caterpillar to cut up to 5000 jobs by end of 2016, stock falls 6%