动态规划法求解矩阵中最长的递增路径的长度

2018-05-28

给定一个整数矩阵,找到增加最长路径的长度。

从每一个单元格,你可以移到四个方向:左,右,向上或向下。你不能移到对角线移动或移动以外的边界(即缠绕是不允许的)。

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4 The longest increasing path is [1, 2, 6, 9]. Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed. Here is my code

/**
 * 
 */
package com.zhazhapan.algorithm.dynamicprogramming;

import java.util.Arrays;


/**
 * @author pantao
 * @date 2017-04-04
 *
 */
public class PathProblem {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] test={{1,6,12,1,3},{8,4,6,10,5},{12,11,7,12,2},{2,3,4,1,13},{14,6,0,14,13}};
        System.out.println(longestIncreasingPath(test));
    }

    static int[][] Lens;

    public static int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        Lens = new int[matrix.length][matrix[0].length];
        int pathLen = 0;
        for (int i = 0; i < Lens.length; i++) {
            for (int j = 0; j < Lens[i].length; j++) {
                Lens[i][j] = -1;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                pathLen = Math.max(pathLen, requestPathLength(matrix, i, j));
            }
        }
        return pathLen + 1;
    }
    public static int requestPathLengths(int[][] matrix, int i, int j) {
        if (Lens[i][j] != -1) {
            return Lens[i][j];
        }
        int a = 0;
        if (i - 1 > -1 && matrix[i][j] < matrix[i - 1][j]) {
            a = 1 + requestPathLength(matrix, i - 1, j);
        }
        int b = 0;
        if (i + 1 < matrix.length && matrix[i][j] < matrix[i + 1][j]) {
            b = 1 + requestPathLength(matrix, i + 1, j);
        }
        int c = 0;
        if (j - 1 > -1 && matrix[i][j] < matrix[i][j - 1]) {
            c = 1 + requestPathLength(matrix, i, j - 1);
        }
        int d = 0;
        if (j + 1 < matrix[0].length && matrix[i][j] < matrix[i][j + 1]) {
            d = 1 + requestPathLength(matrix, i, j + 1);
        }
        Lens[i][j] = Math.max(Math.max(a, b), Math.max(c, d));
        return Lens[i][j];
    }
}