Card Game

https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/card_game.html

Given series of card and a number K, if there are three consecutive cards a, b and c conforms that a + K = b and b + K = c, we can drop the three cards off. Then after serveral round of dropping, what's the least possible number of cards remains (which can not be drop any more).

+

This is a dynamic programming problem. Let DP[i][j] is the minimum number of cards remains after dropping cards in str[i..j] (i, j inclusive), then we can write the following iterate formular:

DP[i][j]=mini≤k<j{DP[i][k]+DP[k+1][j]}

What's more, when cards[i] + K = cards[k] and cards[k] + K = cards[j] as well as DP[i+1][k−1]=DP[k+1][j−1]=0 we have DP[i][j]=0.

We can compress the space cost of DP matrix, but by doing so, the iteration order to calculate the values is very important and should be handled with attention.

    private static int solve(int[] array, int N, int K) {
        int[][] DP = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                DP[i][j] = j - i + 1;
            }
        }
        for (int r = 2; r < N; r++) {
            for (int l = r - 2; l >= 0; l--) {
                int min = DP[l][r];
                for (int m = l; m < r; m++) {
                    min = Math.min(min, DP[l][m] + DP[m + 1][r]);
                }
                for (int m = l + 1; m < r; m++) {
                    if (array[l] + K != array[m] || array[m] + K != array[r]) continue;
                    int lmin = DP[l + 1][m - 1];
                    int rmin = DP[m + 1][r - 1];
                    if (lmin == 0 && rmin == 0) {
                        min = 0;
                    } 
                }
                DP[l][r] = min;
            }
        }
        return DP[0][N - 1];
    }