Leetcode 100361100367.切割蛋糕的最小总开销

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;}
};