Longest Common Subsequence II

题目
Given two sequence P and Q of numbers. The task is to find Longest Common Subsequence of two sequence if we are allowed to change at most k element in first sequence to any value.

Example
Given P = [8 ,3], Q = [1, 3], K = 1
Return 2

Given P = [1, 2, 3, 4, 5], Q = [5, 3, 1, 4, 2], K = 1
Return 3

答案

public class Solution {
    /**
     * @param P: an integer array P
     * @param Q: an integer array Q
     * @param k: the number of allowed changes
     * @return: the length of lca with at most k changes allowed.
     */
    public int longestCommonSubsequenceTwo(int[] P, int[] Q, int K) {
        // write your code here
        int m = P.length, n = Q.length;
        //System.out.println("m = " + Integer.toString(m) + " n = " + Integer.toString(n));
        // f[i][j][k]: LCS(P[0...i-1], Q[0...j-1], k)
        int[][][] f = new int[m + 1][n + 1][K + 1];

        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= K; k++) {
                    // LCS of any string with empty string is 0
                    if(i == 0 || j == 0) {
                        //System.out.println("i = " + Integer.toString(i) + " j = " + Integer.toString(j) + " k = " + Integer.toString(k));
                        f[i][j][k] = 0;
                        continue;
                    }

                    if(P[i - 1] == Q[j - 1])
                        f[i][j][k] = 1 + f[i - 1][j - 1][k];
                    else {
                        f[i][j][k] = Math.max(f[i][j - 1][k], f[i - 1][j][k]);
                        if(k > 0)
                            f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - 1][k - 1] + 1);
                    }

                }

            }
        }
        return f[m][n][K];
    }
}