Coordibate-based DP Problem

Subproblems can be represented as one or two dimensional coordinates.

Triangle

Analysis:

• Subproblem: Minimum path sum ending at corresponding point, stored in another 2-dimentional array

• Initialize: Start point, and points on left and right edges of the triangle

• Function: Math.min(path[i-1][j-1], path[i-1][j])+triangle[i][j]

• Answer: Min value on the bottom edge

public int minimumTotal(int[][] triangle) {

        if (triangle == null || triangle.length == 0 || triangle[0].length == 0)
            return 0;

        int M = triangle.length;
        int[][] path = new int[M][M];

        // Initialize
        path[0][0] = triangle[0][0];
        for (int i=1; i<M; i++) {
            path[i][0] = path[i-1][0]+triangle[i][0];
            path[i][i] = path[i-1][i-1]+triangle[i][i];
        }
        // Function
        for (int i=2; i<M; i++){
            for (int j=1; j<i; j++) {
                path[i][j] = Math.min(path[i-1][j-1], path[i-1][j])+triangle[i][j];
            }
        }
        // Answer: minimum of last level
        int min = path[M-1][0];
        for (int j=1; j<M; j++){
            min = path[M-1][j]<min?path[M-1][j]:min;
        }
        return min;
    }

Longest Increasing Subsequence(LIS)

Analysis:

• Subproblem: Max length of LIS ending at corresponding point

• Initialize: Start point to be 1

• Function: f[i]=Max(f[j]+1), j<i && nums[i]>nums[j]

• Answer: Max{f(0,...,n-1)}

public int longestIncreasingSubsequence(int[] nums) {

        if (nums == null || nums.length == 0)
            return 0;

        int M = nums.length;
        int[] count = new int[M];
        int max = 0;

        // Initialize
        count[0] = 1;
        // Function
        for (int i=1; i<M; i++) {
            count[i] = 1;
            for (int j=i-1; j>=0; j--) {
                if (nums[i] > nums[j]){
                    count[i] = Math.max(count[j]+1, count[i]);
                }
            }
            max = Math.max(max, count[i]);
        }

        // Answer: maximum of the count sequence
        return max;
    }