算法【Java】—— 动态规划之简单多状态 dp 问题

按摩师

https://leetcode.cn/problems/the-masseuse-lcci

状态表示：根据经验和题目要求，达到 i 位置的时候，预约时间最长

接着我们细分状态表示：在遍历数组的时候，到达 i 位置的时候，又两种情况，要么接收预约，要么不接受预约。这里有两种状态，可以使用一个二维 dp 表，这里使用两个 dp 表，一个是 f[i] 说明接受预约，g[i] 说明不接受预约。

状态转移方程推导：f[i] 说明在 i 位置接受了预约，那么 i - 1 就不能接受预约，因为按摩师不接受相邻的位置的预约。那么在 i 位置最大预约时间应该等于 i - 1 位置最大预约时长加上 nums[i] 位置 即 f[i] = g[i-1] + nums[i]
g[i] 说明 i 位置不接受预约，那么 i - 1 位置就有两种情况，要么接受预约，要么不接受预约，我们取者两种情况的最大值。g[i] = max(f[i-1], g[i-1]);

初始化：由于用到了前一个的节点，为了避免填表的越界访问，所以将第一个节点初始化一下（f[0] = nums[0], g[0] = 0;），然后从第二个节点开始填表

填表顺序：从左到右，两个表同时填

返回两个表最后一个节点的最大值

class Solution {
    public int massage(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0];
        for(int i = 1; i < n; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(g[i-1], f[i-1]);
        }
        return Math.max(f[n-1], g[n-1]);
    }
}

打家劫舍Ⅱ

https://leetcode.cn/problems/house-robber-ii

解析：
这里就是首尾不能同时偷，除去首位两个位置，其他位置本质上和我们上一题的按摩师是一样的。

我们可以封装一个方法，该方法放多两个参数，也就是起始位置和终止位置，在此范围进行打家劫舍。

进行分类讨论，当偷了第一个节点的时候，我们只能从第三个节点到倒数第二个节点之间进行偷取，如果不偷第一个节点，我们可以从第二个节点到最后一个节点进行偷取。

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n-1));
    }
    int rob1(int[] nums, int left, int right) {
        if(left > right) {
            return 0;
        }
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left] = nums[left];
        for(int i = left + 1; i <= right; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(g[i-1], f[i-1]);
        }
        return Math.max(g[right], f[right]);
    }
}

删除并获得点数

https://leetcode.cn/problems/delete-and-earn

解析：
我们可以先对数组排个序，或者使用数组来模拟哈希表来存储数据方便我们进行删除操作。无论是哪种形式，最后数据一定是有序的，接着就是我们的动态规划了。

题目说如果删除了 nums[i], 就要连通 nums[i] +1 和 nums[i] - 1 一起删除，和上面的打家劫舍很相似，也就是我偷了这个位置的数值之后，相邻两边的数值是不能在偷了。

状态表示：当达到 i 位置的时候，要么删除获得当前最大点数，要么不删除获得当前最大点数，使用两个 dp 表来存储状态值。f[i] 表示删除 i 位置获得最大点数，g[i] 表示不删除 i 位置获得最大点数。

状态转移方程：f[i] = g[i-1] + i 位置的点数
g[i] = max(f[i-1], g[i-1])

初始化，由于要用到前一个节点，为了避免填表的越界访问，所以将第一个节点初始化一下。初始化 f[0 = arr[0] * 0 = 0, g[0] = 0

填表顺序：从左到右，两表同时填写

返回两个表最后一个节点的最大值

参考代码：

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = 10001;
        int[] arr = new int[n];
        for(int x : nums) {
            arr[x]++;
        }
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 1; i < n; i++) {
            f[i] = g[i-1] + arr[i] * i;
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        return Math.max(f[n-1], g[n-1]);
    }
}

粉刷房子

https://leetcode.cn/problems/JEj789

解析：
状态表示：还是和之前的思路一样，到达 i 位置 的时候，当前的粉刷费用最低。
还可以细分，达到 i 位置有三种刷法，红色，蓝色，绿色。那就是三个 dp 表，我们可以建一个二维的 dp 表即 dp[n][3]，dp[i][0] 表示 i 位置刷成红色时费用最低，dp[i][1] 表示 i 位置刷成蓝色费用最低，dp[i][2] 表示 i 位置刷成绿色费用最低。

状态转移方程：由于相邻两个位置不能颜色相同，所以 dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + 对应的 i 位置的红色费用，dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + 对应的 i 位置的蓝色费用，dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + 对应的 i 位置的绿色费用

初始化，因为要用到前一个节点的数值，为了避免填表的越界访问，所以将第一个节点初始化一下。dp[0][0] = costs[0][0]，dp[0][1] = costs[0][1]，dp[0][2] = costs[0][2]

填表顺序：从左到右，两表同时填

返回值，遍历 dp 表最后一行返回最小值。

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

买卖股票的最佳时期

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown

解析：
状态表示：第 i 天结束的时候，获得最大利润。

细分状态表示：第 i 天结束的时候要么持有股票，要么没有股票，持有股票处于 “买入” 状态，没有股票要么处于冷静期（此时不能购买股票），要么处于 "可交易” 状态（可以买股票），那么一共有三种状态，我们使用一个二维的 dp 表 dp[n][3] ，dp[i][0] 表示 “买入”状态，dp[i][1] 表示 ”冷静期“ 状态，dp[i][2] 表示 ”卖出“ 状态。

当状态比较复杂的时候，我们可以画个图：

解释一下箭头的含义，箭头的起始位置表示第 i 天的开始，然后箭头的 身体表示 第 i 天做了什么操作，箭头最后指向的就是第 i 天结束的时候达到的状态。

这个图还有个名字叫做 “状态机”，根据图我们可以很容易地写出状态转移方程：
dp[i][0] = max(dp[i-1][0]，dp[i-1][2] - prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][1], dp[i-1][2])

初始化，由于要用到前一行的状态值，所以要初始化第一行，避免后面填表的越界访问。

填表顺序：从上到下，从左到右，三表同时填。

返回值：返回 dp 表最后一个的最大利润值，还可以再简化一下，返回 Math.max(dp[i][1], dp[i][2])，因为最后一天还持有股票的话，是不可能达到利润的最大值。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
        }
        return Math.max(dp[n-1][1], dp[n-1][2]);
    }
}

买卖股票的最佳时期含手续费

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

解析：
这里有个手续费的操作，我们设置每次把股票卖出去的时候算作一次交易，也就是在卖出股票的时候才扣除手续费 fee

状态表示：第 i 天结束的时候，利润最大。
继续细分状态，第 i 天结束的时候，要么持有股票（设为“买入”状态），要么没有股票（设为“卖出”状态），使用 二维 dp 表 dp[n][2] 来表示， dp[i][0] 表示 “买入”状态，dp[i][1] 表示 “卖出” 状态。

当状态多的时候，我们可以画个图：

状态转移方程:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)

初始化第一行：dp[0][0] = -prices[0]; dp[0][1] = 0;

填表顺序：从上到下，从左到右

返回dp[n-1][1]

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
        }
        return dp[n-1][1];
    }
}

买卖股票的最佳时机 Ⅲ

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii

解析：
状态表示：第 i 天结束的时候，获得最大利润

接着细分状态表示，第 i 天结束的时候，要么持有股票，要么不持有股票，并且由于题目有要求最多进行两笔交易，我们这里定义卖出股票的时候算作一笔交易，那么还要有一个状态就是这是 第 几笔交易

那么我们重新定义状态：第 i 天结束的时候，持有股票（处于“买入”状态），这是第 j 笔交易，并且利润最大，使用 f[i][j] 二维 dp 表表示
第 i 天结束的时候，没有股票（处于“卖出”状态），这是第 j 笔交易，并且利润最大，使用 g[i][j] 二维 dp 表表示

画个状态机：

状态转移方程：
f[i][j] = max(f[i-1][j]，g[i-1][j] - prices[i])
g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i])

初始化：
上面两个状态转移方程都需要用到前一行的状态值，所以将第一行初始化一下，首先 f 表来，f 表表示 “买入” 状态，要想买入，就必须买下第 0 天的股票 即 f[0][0] = -prices[i]，f[0] 这一行的其他列是没有数值的，因为第 0 天的交易笔数是 0，所以剩下的空位必须保证不能影响到第二行的填表，此时应该设置为 无穷小

接着就是 g 表，表示 “卖出状态”，第 0 天 第 0 笔交易没有股票卖出，只能 为 0，即 g[0][0] = 0，第 0 行 剩余的其他空位要不影响到 g 表下一行的填写，所以应该设置为 无穷小。

注意：无穷小不能直接定义为 Integer.MIN_VALUE，因为 f[i][j] = max(f[i-1][j]，g[i-1][j] - prices[i]) 其中的 g[i-1][j] - prices[i] 这个式子，如果为 Integer.MIN_VALUE 的话，一减会发生溢出现象或者运行报错，所以这里的无穷小，一般我们设置为 0x3f3f3f

细节处理：因为g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]) 中要用到 f[i-1][j-1]， 这可能会发生越界，所以我们填表的时候可以加一个 判断条件 if(j-1 >= 0) 才进行 max 的比较，如果 j - 1 小于 0 ，说明对应的 f 状态值不存在，直接将 g[i-1][j] 赋值给 g[i][j]

i 表示天数，所以直接是 prices.length 行，那多少列合适呢？题目告诉我们最多有两笔交易，所以应该是 3 列（0 笔交易，1 笔交易，2 笔交易），所以 f 表和 g 表应该为 n 行 3 列

填表顺序：从上到下，从左到右，双表一起填

返回值，遍历 g 表最后一行，返回最大值

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        for(int i = 1; i < 3; i++) {
            f[0][i] = g[0][i] = -0x3f3f3f;
        }
        f[0][0] = -prices[0];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if(j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i]);
                }
            }
        }
        int ret = 0;
        for(int i = 0; i < 3; i++) {
            ret = Math.max(ret, g[n-1][i]);
        }
        return ret;
    }
}

买卖股票的最佳时机 Ⅳ

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv

解析和上面一题是一样的，这里不赘述了，交给大家练手了。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][k+1];
        int[][] g = new int[n][k+1];
        for(int j = 1; j <= k; j++) {
            f[0][j] = g[0][j] = -0x3f3f3f;
        }
        f[0][0] = - prices[0];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if(j-1 >= 0) 
                    g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i]);
            }
        }
        int ret = 0;
        for(int j = 0; j <= k; j++) {
            ret = Math.max(ret, g[n-1][j]);
        }
        return ret;
    }
}