x******8
发帖数: 48 | 1 Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
不能对角线，找出长度或者移动路径，这个怎么做？brutal force? |
h*********o
发帖数: 230 | 2 应该也还是DP吧 上下左右比较~~
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
|
b***e
发帖数: 1419 | 3 先排序，然后从大往小DP。
【在 x******8 的大作中提到】
: Longest Increasing Sequence 2D matrix 二维数组最长递增子序列，只能上下左右，
: 不能对角线，找出长度或者移动路径，这个怎么做？brutal force?
|
j********g
发帖数: 80 | |
x******8
发帖数: 48 | 5 连续的，请问怎么做？
【在 j********g 的大作中提到】
: 连续的么 ， 连续的好做 不连续的可能比较麻烦
|
x******8
发帖数: 48 | 6 排序？请问怎么排序？
【在 b***e 的大作中提到】
: 先排序，然后从大往小DP。
|
b***e
发帖数: 1419 | 7 从大到小排序，记住位置。
【在 x******8 的大作中提到】
: 排序？请问怎么排序？
|
x******8
发帖数: 48 | 8 能讲下具体思路吗？
【在 h*********o 的大作中提到】
: 应该也还是DP吧 上下左右比较~~
|
b*****n
发帖数: 618 | 9 recursion + memorization就行了吧，最简单直观的方法。
排序有什么太大的必要么，空间复杂度也没降。
对每个格子，看它四个方向的邻居组成的最长递增序列是多长，如果之前已经算过了就
不用再算了，如果没算过就recursion算一下 |
z***m
发帖数: 1602 | |
a********m
发帖数: 15480 | 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?
|
a********m
发帖数: 15480 | 12 不用排序。dp本质上是暴力的。
【在 b***e 的大作中提到】
: 先排序，然后从大往小DP。
|
x******8
发帖数: 48 | |
