Poj_1088_滑雪(DP)

一、Description(poj1088)

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

二、问题分析

典型的DP问题，动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

解这个问题与解其它的DP问题几乎没有什么两样。第一步找到问题的“状态”，第二步找到“状态转移方程”，然后基本上问题就解决了。首先，我们要找到这个问题中的“状态”是什么？我们必须注意到的一点是，到达一个坐标的方式最多有四种：上下左右四个方向，而且值必须必坐标值要大。然后再从这四个来源中选取符合要求的点，并从中选出S[i][j]最大的，也就是路径长度最长的，而所选出的这个坐标又可以当成是一个子问题递归求解。由于使用了记忆化存储，所以可以先直接查表，如果表中存在子问题的解则直接返回，否则就按上面的分析过程找到最大路径并存储。经过上面的分析，很容易可以得出问题的状态和状态转移方程。

S[i][j]=1 + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0；S[i+1][j] , if i<m-1 ; S[i][j+1], if j<n-1 )

三、解决方案

有了上面的分析，编码就比较简单了。用一个二维数组用于读取坐标，再用一个二维数组用于记忆化存储。再写一个方法计算每一个坐标的值，并从四个方向分析上一步的最大值，并递归调用方法。算出本坐标的最大值并存储。最后，找出S数组中的最大值即是所求的最大路径。

import java.util.Scanner;
public class N1088_skate{
  private int h[][]=new int[101][101];
  private int m[][]=new int[101][101];
  private int r,c;

  private void init(){
    Scanner sc=new Scanner(System.in);
    r=sc.nextInt();
    c=sc.nextInt();     
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++){
            h[i][j]=sc.nextInt();
    		m[i][j]=-1;
        }
  }

  //递归获取从点(i,j)出发滑行的最大长度
  public int searchWithMenmo(int x,int y){
		if( m[x][y]!=-1)
		    return m[x][y];
		else{
			int max=0;
			if(x>=1){
				if(h[x-1][y]>h[x][y]){
					max=Math.max(max,searchWithMenmo(x-1,y));
				}
			}
			if(y>=1){
				if(h[x][y-1]>h[x][y]){
					max=Math.max(max,searchWithMenmo(x,y-1));
				}
			}
			if(x<r-1){
				if(h[x+1][y]>h[x][y]){
					max=Math.max(max,searchWithMenmo(x+1,y));
				}
			}
			if(y<c-1){
				if(h[x][y+1]>h[x][y]){
					max=Math.max(max,searchWithMenmo(x,y+1));
				}
			}
			m[x][y]=max+1;
			return m[x][y];
	}
  }

 public int getMaxHeight(){
   int temp;
   int Max=-1;
   for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            temp=searchWithMenmo(i,j);
            if(Max< temp)
                Max=temp;    
        }
    }
    return Max;
  }
  public static void main(String args[]){
    N1088_skate m=new N1088_skate();
    m.init();
    System.out.println(m.getMaxHeight());
  	}
}