Card Game

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]=\min_{i\le k<j}\left\{ DP[i][k]+DP[k+1][j]\right\}$$

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.

import java.io.*;
import java.util.*;

public class CardGame {
    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];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int N = in.nextInt(), K = in.nextInt();
            int[] array = new int[N];
            for (int i = 0; i < N; i++) {
                array[i] = in.nextInt();
            }
            System.out.printf("Case #%d: %d\n", t + 1, solve(array, N, K));
        }
    }
}