Most Intutive O(N^2) Java DP Solution


  • 0
    S

    Similar to the Problem #300 longest increase sequence, beyond that use a array cnt[] to recode the ways to arrive lis[i] (lis end at a[i)]. Here is the solution.

    static int numOfLIS(int[] a) {
    		if (a == null || a.length == 0)	return 0;
    		if (a.length < 2)	return 1;
    		int[] dp = new int[a.length];
    		Arrays.fill(dp, 1);
    		int maxLen = 1;
    		
    		int[] cnt = new int[a.length];	// cnt[i]: the ways that arrive the LIS end at a[i]
    		Arrays.fill(cnt, 1);
    		int res = 0;
    		for (int i = 1; i < a.length; i++) {
    			for (int j = i-1; j >= 0; j--) {
    				if (a[i] > a[j] && dp[j]+1 > dp[i])
    					dp[i] = dp[j]+1;
    			}
    			if (maxLen < dp[i]) maxLen = dp[i];
    
    			// compute cnt[i]
    			if (dp[i] > 1) {	// dp[i] has changed from original 1 after traverse [0, i-1]
    				cnt[i] = 0;	// for updated dp[i], cnt[i] is initialed as 0
    				for (int j = i-1; j >= 0; j--) {
    					if (a[i] > a[j] && dp[j]+1 == dp[i])
    						cnt[i] += cnt[j];
    				}
    			}
    		}
    		for (int i = 0; i < a.length; i++) {
    			if (dp[i] == maxLen) {
    				res += cnt[i];
    			}
    		}
    		return res;
    	}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.