DP题目总结

1、LC1388. 3n 块披萨

题意：

• 3n的环形数组，每次取一个数后就删除前后相邻的两个数，问最后取得的总数最大是多少。

分析:

• 相当于不能取相邻数（打家劫舍问题），但这里是环形的，所以要拆成一个去掉第一个数的数组，一个去掉最后一个数的数组。算两次取最大值

代码

class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        int k = n / 3;
        int dp[n][2][k + 1];
        memset(dp, 0, sizeof(dp));
        int res = 0;

        // 去掉第一个数
        dp[1][1][1] = slices[1];
        for(int i = 2; i < n; ++ i) {
            for(int j = 1; j <= k; ++ j) {
                dp[i][0][j] = max(dp[i - 1][0][j], dp[i - 1][1][j]);
                dp[i][1][j] = dp[i - 1][0][j - 1] + slices[i];
            }
        }
        res = max(res, max(dp[n - 1][0][k], dp[n - 1][1][k]));
        
        //去掉最后一个数
        memset(dp, 0, sizeof(dp));
        dp[0][1][1] = slices[0];
        for(int i = 1; i < n - 1; ++ i) {
            for(int j = 1; j <= k; ++ j) {
                dp[i][0][j] = max(dp[i - 1][0][j], dp[i - 1][1][j]);
                dp[i][1][j] = dp[i - 1][0][j - 1] + slices[i];
            }
        }
        res = max(res, max(dp[n - 2][0][k], dp[n - 2][1][k]));
        return res;
    }
};