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 | |