1335. Minimum Difficulty of a Job Schedule

decreasing stack + dp O(nd) time O(n) space
f[i]表示经过day天后截至jobDifficulty[i]的最小困难结果，即f[day][i]
因为f[day][i] = min{f[day - 1][j] + max{jobDifficulty[j + 1 : i]}}，假设jobDifficulty[j]是jobDifficulty[i]左边第一个更大的数，则max{jobDifficulty[j + 1 : i]} = jobDifficulty[i]
f[day][i] = min{f[day][j], min{f[day - 1][j + 1 : i - 1]} + jobDifficulty[i]}
因为jobDifficulty[j] > jobDifficulty[i]，所以f[day][j]的最后一个区间一定也可以cover整个jobDifficulty[j + 1 : i]区间，且根据归纳法f[day][j]一定不会比f[day - 1][j] + jobDifficulty[i]更差
找jobDifficulty[j]左边第一个更大的jobDifficulty[i]可以用单调栈，求min{f[day - 1][j + 1 : i - 1]}可以利用单调栈顺便保存每个小区间的前一天的最小困难结果，具体而言，如果单调栈所存下标为 k₁,k₂,…,k_n，则在 k₁的位置上额外存储区间[0, k₁)的最小值，在k₂的位置上额外存储区间[k₁, k₂)的最小值，以此类推

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n);
        f[0] = jobDifficulty[0];
        for (int i = 1; i < n; ++i) {
            f[i] = max(f[i - 1], jobDifficulty[i]); // 先算出第一天后的结果
        }
        vector<int> t(n);
        for (int day = 1; day < d; ++day) { // d是1-based改成0-based
            swap(t, f);
            stack<pair<int, int>> s; // <区间最小困难结果，下标>
            for (int i = day; i < n; ++i) {
                int p = t[i - 1]; // 初始化为前一天截至jobDifficulty[i - 1]的最小困难结果
                while (!empty(s) && jobDifficulty[s.top().second] <= jobDifficulty[i]) {
                    p = min(p, s.top().first); // 用前一天前一个区间的最小困难结果来更新
                    s.pop();
                }
                if (empty(s)) {
                    f[i] = p + jobDifficulty[i]; // min{f[day - 1][0 : i - 1]} + jobDifficulty[i]
                } else {
                    f[i] = min(p + jobDifficulty[i], f[s.top().second]); // min{f[day][j], min{f[day - 1][j + 1 : i - 1]} + jobDifficulty[i]}
                }
                s.emplace(p, i);
            }
        }
        return f[n - 1];
    }
};

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n);
        f[0] = jobDifficulty[0];
        for (int i = 1; i < n; ++i) {
            f[i] = max(f[i - 1], jobDifficulty[i]);
        }
        vector<int> t(f);
        for (int day = 1; day < d; ++day) {
            swap(t, f);
            vector<array<int, 3>> s{{M, M, M}};
            for (int i = day; i < n; ++i) {
                int p = t[i - 1];
                while (s.back()[1] <= jobDifficulty[i]) {
                    p = min(p, s.back()[0]);
                    s.pop_back();
                }
                s.push_back({p, jobDifficulty[i], min(p + jobDifficulty[i], s.back()[2])});
                f[i] = s.back()[2];
            }
        }
        return f[n - 1];
    }
};

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n, M), t(n);
        for (int day = 0; day < d; ++day) {
            swap(t, f);
            stack<int> s;
            for (int i = day; i < n; ++i) {
                f[i] = i > 0 ? t[i - 1] + jobDifficulty[i] : jobDifficulty[i];
                while (!empty(s) && jobDifficulty[s.top()] <= jobDifficulty[i]) {
                    f[i] = min(f[i], f[s.top()] - jobDifficulty[s.top()] + jobDifficulty[i]);
                    s.pop();
                }
                if (!empty(s)) {
                    f[i] = min(f[i], f[s.top()]);
                }
                s.push(i);
            }
        }
        return f[n - 1];
    }
};

bottom-up dp O(nnd) time O(nd) space
f[day][i]表示到第day天安排前i个job的最小难度
转移方程为
f[day][i] = min{f[day - 1][j] + max{jobDifficulty[j : i - 1]}} where j ~ [day - 1, i - 1]
初始化
f[0][0] = 0表示到第0天安排前0个job的最小难度为0
其他都为inf，在之后的计算过程中凡是有f[day][i] where i < day的理论上都应该为inf
最终结果
f[d][n]
计算顺序
从前往后扫每天day，对于每天day，从前往后遍历每个i，再对每个i从后往前尝试每个j

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<vector<int>> f(d + 1, vector<int>(n + 1, M));
        f[0][0] = 0;
        for (int day = 1; day <= d; ++day) {
            for (int i = day; i <= n; ++i) {
                int mx = INT_MIN;
                for (int j = i - 1; j >= day - 1; --j) { // j >= 0也可以但是实际上应该是j >= day - 1因为不可能出现比day - 1更小的j
                    mx = max(mx, jobDifficulty[j]);
                    f[day][i] = min(f[day][i], f[day - 1][j] + mx);
                }
            }
        }
        return f[d][n];
    }
};

rolling array优化
O(nnd) time O(n) space
需要注意的是计算每个f[day][i]之前必须要重置为inf

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<vector<int>> f(2, vector<int>(n + 1, M));
        f[0][0] = 0;
        for (int day = 1; day <= d; ++day) {
            int dd = day & 1;
            for (int i = day; i <= n; ++i) {
                int mx = INT_MIN;
                f[dd][i] = M;
                for (int j = i - 1; j >= day - 1; --j) {
                    mx = max(mx, jobDifficulty[j]);
                    f[dd][i] = min(f[dd][i], f[dd ^ 1][j] + mx);
                }
            }
        }
        return f[d & 1][n];
    }
};

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<vector<int>> f(2, vector<int>(n + 1, M));
        f[0][0] = 0;
        for (int day = 1; day <= d; ++day) {
            for (int i = day; i <= n; ++i) {
                int mx = INT_MIN;
                f[day & 1][i] = M;
                for (int j = i - 1; j >= day - 1; --j) {
                    mx = max(mx, jobDifficulty[j]);
                    f[day & 1][i] = min(f[day & 1][i], f[(day - 1) & 1][j] + mx);
                }
            }
        }
        return f[d & 1][n];
    }
};

一维数组优化
O(nnd) time O(n) space
注意到每一行只跟前一行有关，对于每天day，可以改成从后往前遍历每个i，再对每个i从后往前尝试每个j

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = size(jobDifficulty);
        if (n < d) return -1;
        int M = 3e5 + 1;
        vector<int> f(n + 1, M);
        f[0] = 0;
        for (int day = 1; day <= d; ++day) {
            for (int i = n; i >= day; --i) {
                f[i] = M;
                int mx = INT_MIN;
                for (int j = i - 1; j >= day - 1; --j) {
                    mx = max(mx, jobDifficulty[j]);
                    f[i] = min(f[i], f[j] + mx);
                }
            }
        }
        return f[n];
    }
};