题目
题目来源：Link
分析
1、自底向上
（1）对原始数据排序成List
（2）遍历List，从最小的 x 开始计算路径
（3）对于当前遍历的节点 x , 检查其四周的点，如果四周点大于自身且 x 路径长+1 大于四周点记录的当前记录的最大路径长，则更新其路径值及路径来源
（4）记录路径最大点位置
（5）根据最大点位置重构路径
2、备忘录的自顶向下
（1）遍历数组
（2）根据 flag[i][j] 如果 dp[i][j] 的值已经确定，则不用再计算，直接返回 dp[i][j]
（3）如果dp[i][j] 的值没有确定，则递归下去继续求解子问题
代码
package com.graph;
import java.util.*;
import org.omg.CORBA.INTERNAL;
public class Solution {
int[][] nums;
//方法二：自底向上
//TC=O(n*m)
//动态规划，自底向上
public void solve_downUp(int[][] nums){
List<Integer> res = new ArrayList<Integer>();
//special cases
if(nums==null || nums.length==0) return;
this.nums = nums;
//sort the nums
List<Position> list = new ArrayList<Position>();
int n = nums.length;
int m = nums[0].length;
//TC=O(n*m)
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
list.add(new Position(nums[i][j], i, j));
}
}
Collections.sort(list, new Comparator<Position>(){
@Override
public int compare(Position a, Position b){
if(a.val>b.val)
return 1;
else if(a.val<b.val)
return -1;
else
return 0;
}
});
//build
record = new Record[n][m];
maxp = new Position(list.get(0).val,list.get(0).x,list.get(0).y);
max = 1;
//init record
//TC=O(n*m)
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
record[i][j] = new Record();
}
}
//TC=O(n*m)
for(int k=0; k<m*n; k++){
Position tmp = list.get(k);
int i;
int j;
//上
i = tmp.x-1;
j = tmp.y;
if(i>=0&&i<n && j>=0&&j<m)
updateRecord(i,j,tmp);
//下
i = tmp.x+1;
j = tmp.y;
if(i>=0&&i<n && j>=0&&j<m)
updateRecord(i,j,tmp);
//左
i = tmp.x;
j = tmp.y-1;
if(i>=0&&i<n && j>=0&&j<m)
updateRecord(i,j,tmp);
//右
i = tmp.x;
j = tmp.y+1;
if(i>=0&&i<n && j>=0&&j<m)
updateRecord(i,j,tmp);
}
//recostruct the result
Record re = record[maxp.x][maxp.y];
StringBuffer tt = new StringBuffer();
while(re.from!=null){
//System.out.print(nums[maxp.x][maxp.y]);
tt.append(nums[maxp.x][maxp.y]);
maxp = re.from;
re = record[maxp.x][maxp.y];
}
tt.append(nums[maxp.x][maxp.y]);
System.out.print(tt.reverse().toString());
}
Record[][] record;
Position maxp;
int max;
public void updateRecord(int i, int j, Position tmp){
if(nums[i][j]>tmp.val){
int con = record[tmp.x][tmp.y].pn+1;
if(con>record[i][j].pn){
record[i][j].pn = con;
record[i][j].from = new Position(tmp.val,tmp.x,tmp.y);
if(con>max){
max=con;
maxp=new Position(nums[i][j],i,j);
}
}
}
}
class Record{
public Position from=null;
public int pn=1;
}
class Position{
public int val;
public int x;
public int y;
public Position(int val, int x, int y){
this.val = val;
this.x = x;
this.y = y;
}
}
//方法二：备忘录的自顶向下
int[][] dp;
int[][] flag;
int n,m;
public void solve_upDown(int[][] nums) {
if(nums==null || nums.length==0) return;
this.nums = nums;
n = nums.length;
m = nums[0].length;
dp = new int[n][m];
flag = new int[n][m];
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
dp[i][j] = search(i,j);
}
}
}
int[] dx = {-1,0,1,0};
int[] dy = {0,1,0,-1};
public int search(int i, int j) {
int res=1;
if(flag[i][j]!=0) {
return dp[i][j];
}
//检查四周
//int maxk=0;
for(int k=0; k<4; k++) {
int x = i+dx[k];
int y = j+dy[k];
if(i>=0&&i<n && j>=0&&j<m) {
if(nums[i][j]>nums[x][y]) {
res = Math.max(res, search(x, y)+1);
}
}
}
flag[i][j]=1;
dp[i][j]=res;
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
s.solve_downUp(new int[][] {{9,9,4},{6,6,8},{2,1,1}});
}
}
