DP 최적화 — 공간 압축, 비트마스크 DP, 분할 정복 최적화

// 2차원 dp[n][m]을 2개 행으로 압축
// 이전 행(prev)과 현재 행(curr)만 사용
int[] prev = new int[m + 1];
int[] curr = new int[m + 1];

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        curr[j] = computeFromPrev(prev, curr, i, j);
    }
    // 행 스왑
    int[] temp = prev;
    prev = curr;
    curr = temp;
    Arrays.fill(curr, 0);
}

// 0/1 배낭: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt] + val)
// dp[i-1][w-wt]를 참조 → 작은 인덱스 → 역순 순회로 보존
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
    for (int w = capacity; w >= weight[i]; w--) {
        dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

// O(mn) → O(min(m,n))
public static int lcsOptimized(String s1, String s2) {
    if (s1.length() < s2.length()) {
        String temp = s1; s1 = s2; s2 = temp;
    }
    int m = s1.length(), n = s2.length();
    int[] prev = new int[n + 1];
    int[] curr = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                curr[j] = prev[j-1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j-1]);
            }
        }
        int[] temp = prev;
        prev = curr;
        curr = temp;
        Arrays.fill(curr, 0);
    }
    return prev[n];
}

int S = 0b1011;  // {0, 1, 3} 집합 (0-indexed)

// i번째 원소 포함 여부
boolean has = (S & (1 << i)) != 0;

// i번째 원소 추가
S = S | (1 << i);

// i번째 원소 제거
S = S & ~(1 << i);

// 원소 개수
int count = Integer.bitCount(S);

// 부분 집합 순회
for (int sub = S; sub > 0; sub = (sub - 1) & S) {
    // sub는 S의 부분 집합
}

public static int tsp(int[][] dist) {
    int n = dist.length;
    int FULL = (1 << n) - 1; // 모든 도시 방문 상태
    int[][] dp = new int[1 << n][n];

    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    dp[1][0] = 0; // 시작: 도시 0만 방문, 현재 도시 0

    for (int mask = 1; mask <= FULL; mask++) {
        for (int u = 0; u < n; u++) {
            if ((mask & (1 << u)) == 0) continue; // u를 방문하지 않은 상태면 건너뜀
            if (dp[mask][u] == Integer.MAX_VALUE / 2) continue;

            for (int v = 0; v < n; v++) {
                if ((mask & (1 << v)) != 0) continue; // v를 이미 방문했으면 건너뜀

                int nextMask = mask | (1 << v);
                dp[nextMask][v] = Math.min(
                    dp[nextMask][v],
                    dp[mask][u] + dist[u][v]
                );
            }
        }
    }

    // 모든 도시 방문 후 시작점으로 돌아오기
    int result = Integer.MAX_VALUE;
    for (int u = 1; u < n; u++) {
        result = Math.min(result, dp[FULL][u] + dist[u][0]);
    }
    return result;
}

// dp[mask] = mask에 해당하는 일들이 배정된 상태의 최소 비용
// bitCount(mask)번째 사람에게 일을 배정
public static int assignmentProblem(int[][] cost) {
    int n = cost.length;
    int[] dp = new int[1 << n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        int person = Integer.bitCount(mask); // 다음에 배정할 사람
        if (person >= n) continue;

        for (int job = 0; job < n; job++) {
            if ((mask & (1 << job)) != 0) continue;
            int nextMask = mask | (1 << job);
            dp[nextMask] = Math.min(dp[nextMask],
                                     dp[mask] + cost[person][job]);
        }
    }
    return dp[(1 << n) - 1];
}

dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j]  (i < k < j)

opt[i][j] = dp[i][j]의 최적 분할점 k

opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]  (단조성)

// Knuth 최적화 적용 예시
int[][] dp = new int[n + 1][n + 1];
int[][] opt = new int[n + 1][n + 1]; // 최적 분할점

// 기저
for (int i = 0; i < n; i++) opt[i][i] = i;

for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        dp[i][j] = Integer.MAX_VALUE;

        // 탐색 범위 제한!
        for (int k = opt[i][j-1]; k <= opt[i+1][j]; k++) {
            int cost = dp[i][k] + dp[k+1][j] + C(i, j);
            if (cost < dp[i][j]) {
                dp[i][j] = cost;
                opt[i][j] = k;
            }
        }
    }
}

dp[i][j] = min(dp[i-1][k] + C[k+1][j])  (0 ≤ k < j)
opt[i][j] ≤ opt[i][j+1]  (최적 분할점의 단조성)

static void solve(int i, int lo, int hi, int optLo, int optHi) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    int bestK = optLo;
    int bestVal = Integer.MAX_VALUE;

    for (int k = optLo; k <= Math.min(mid - 1, optHi); k++) {
        int val = dpPrev[k] + cost(k + 1, mid);
        if (val < bestVal) {
            bestVal = val;
            bestK = k;
        }
    }
    dpCurr[mid] = bestVal;

    solve(i, lo, mid - 1, optLo, bestK);
    solve(i, mid + 1, hi, bestK, optHi);
}