状态型

状态机约束，作为一层状态

一般定义 f[i][j] 表示前缀 a[:i] 在状态 j 下的最优值。一般 j 都很小。代表题目是「买卖股票」系列。

• 乘积最大子数组

  最大/最小值

• 买卖股票的最佳时机

  是否持有股票

• 粉刷房子

  粉刷哪种颜色

注：某些题目做法不止一种，除了状态机 DP 以外，也有前后缀分解的做法。

256. Paint House

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

• For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

public int minCost(int[][] costs) {
    int n = costs.length;
    int[][] dp = new int[n + 1][3];
    for (int i = 1; i <= n; i++) {
        dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
        dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
        dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
    }

    return Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2]));
}

265. Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x k cost matrix costs.

• For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on...

Return the minimum cost to paint all houses.

public int minCostII(int[][] costs) {
    if (costs.length == 0)
        return 0;

    int n = costs.length, m = costs[0].length; // Fixed: was using costs.length for m
    int[][] dp = new int[n + 1][m];

    for (int i = 1; i <= n; i++) {
        // Precompute minimum and second minimum from previous row
        int minCost = Integer.MAX_VALUE, secondMinCost = Integer.MAX_VALUE;
        int minColor = -1;

        for (int j = 0; j < m; j++) {
            if (dp[i - 1][j] < minCost) {
                secondMinCost = minCost;
                minCost = dp[i - 1][j];
                minColor = j;
            } else if (dp[i - 1][j] < secondMinCost) {
                secondMinCost = dp[i - 1][j];
            }
        }

        // Use precomputed minima to fill current row in O(m)
        for (int j = 0; j < m; j++) {
            if (j == minColor) {
                dp[i][j] = secondMinCost + costs[i - 1][j];
            } else {
                dp[i][j] = minCost + costs[i - 1][j];
            }
        }
    }

    int ans = Integer.MAX_VALUE;
    for (int j = 0; j < m; j++) {
        ans = Math.min(ans, dp[n][j]);
    }

    return ans;
}

3738. Longest Non-Decreasing Subarray After Replacing at Most One Element

You are given an integer array nums.

You are allowed to replace at most one element in the array with any other integer value of your choice.

Return the length of the longest non-decreasing subarray that can be obtained after performing at most one replacement.

An array is said to be non-decreasing if each element is greater than or equal to its previous one (if it exists).

public int longestSubarray(int[] nums) {
    int n = nums.length;
    int[][] f = new int[n][2];
    f[0][0] = f[0][1] = 1;

    int ans = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i - 1] <= nums[i]) {
            f[i][0] = f[i - 1][0] + 1;
            f[i][1] = f[i - 1][1] + 1;
        } else {
            f[i][0] = 1;
            f[i][1] = 1;
        }

        if (i >= 2 && nums[i - 2] <= nums[i]) {
            f[i][1] = Math.max(f[i][1], f[i - 2][0] + 2);
        } else {
            f[i][1] = Math.max(f[i][1], 2);
        }

        ans = Math.max(ans, Math.max(f[i - 1][0] + 1, f[i][1]));
    }
    return ans;
}

public int longestSubarray(int[] nums) {
    int n = nums.length;
    int[][] f = new int[3][2];
    f[0][0] = f[0][1] = 1;

    int ans = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i - 1] <= nums[i]) {
            f[i % 3][0] = f[(i - 1) % 3][0] + 1;
            f[i % 3][1] = f[(i - 1) % 3][1] + 1;
        } else {
            f[i % 3][0] = 1;
            f[i % 3][1] = 1;
        }

        if (i >= 2 && nums[i - 2] <= nums[i]) {
            f[i % 3][1] = Math.max(f[i % 3][1], f[(i - 2) % 3][0] + 2);
        } else {
            f[i % 3][1] = Math.max(f[i % 3][1], 2);
        }

        ans = Math.max(ans, Math.max(f[(i - 1) % 3][0] + 1, f[i % 3][1]));
    }
    return ans;
}

余数

1262. Greatest Sum Divisible by Three

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

public int maxSumDivThree(int[] nums) {
    // dp[i] 表示余数为 i 的最大和
    int[] dp = new int[3];
    Arrays.fill(dp, Integer.MIN_VALUE);
    dp[0] = 0;

    for (int num : nums) {
        int[] nextDp = new int[3];
        for (int i = 0; i < 3; i++) {
            // 两种选择：不选 num (保持原样) vs 选 num (从对应的余数转移过来)
            // 1. 不选 num
            nextDp[i] = dp[i]; 

            // 2. 选 num。我们需要找到之前的余数 r，使得 (r + num) % 3 == i
            // 即 r = (i - num % 3 + 3) % 3
            int prevRemainder = (i - num % 3 + 3) % 3;
            nextDp[i] = Math.max(nextDp[i], dp[prevRemainder] + num);
        }
        dp = nextDp;
    }

    return Math.max(0, dp[0]);
}