Leetcode 100361&100367.切割蛋糕的最小总开销_leetcode蛋糕切割

Medium：动态规划搜索（实际就是优化后的dfs）

class Solution {
public: 
    int f[25][25][25][25] = {0};
    int dp(int row1, int col1, int row2, int col2, vector<int>& horizontalCut, vector<int>& verticalCut){
        if(row1 == row2 && col1 == col2)            // 即该方向上已经无需切割了
            return 0;
        if(f[row1][col1][row2][col2])               // 已经计算过
            return f[row1][col1][row2][col2];
        int cost = 1e9;                             // ☆状态计算划分:为两个部分（横着切or竖着切）
        for(int i = row1; i < row2; i ++)           // 水平方向切割（分割成子问题去求解）
            cost = min(cost, horizontalCut[i] + dp(row1, col1, i, col2, horizontalCut, verticalCut) + dp(i + 1, col1, row2, col2, horizontalCut, verticalCut));
        for(int j = col1; j < col2; j ++)           // 竖直方向进行切割
            cost = min(cost, verticalCut[j] + dp(row1, col1, row2, j, horizontalCut, verticalCut) + dp(row1, j + 1, row2, col2, horizontalCut, verticalCut));
        f[row1][col1][row2][col2] = cost;
        return cost;
    }
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        return dp(0, 0, m - 1, n - 1, horizontalCut, verticalCut);
    }
};

hard：区别在与数据范围，贪心“交换论证法”

证明过程笔记：（两种思考思路）

class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        sort(horizontalCut.begin(), horizontalCut.end(), greater<int>());   // 整理下C++降序排序的两种办法
        sort(verticalCut.begin(), verticalCut.end(), greater<int>());
        int i = 0, j = 0;   // 两个指针,i:横切指针   j:竖切指针
        long long cost = 0;
        int cnth = 1, cntv = 1; // 每次计算当前切割的cost的时候,依赖于前面的横切数/竖切个数
        while(i < m - 1 || j < n - 1){
            if(j >= n - 1 || i < m - 1 && horizontalCut[i] > verticalCut[j]){
                // 代价更大的切割应该放在前面, 故此处应该进行横切
                cost += cntv * horizontalCut[i];
                i ++;
                cnth ++;        // 横切数增加
            }else{// 竖切
                cost += cnth * verticalCut[j];
                j ++;
                cntv ++;        // 竖切数增加
            }
        }
        return cost;
    }
};