LC 3376. Minimum Time to Break Locks I

https://leetcode.com/problems/minimum-time-to-break-locks-i/description/

class Solution {
public:
    int findMinimumTime(vector<int>& strength, int k) {
        int n = strength.size();
        vector<int> f(1 << n, INT_MAX);
        f[0] = 0;
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i < (1 << n); i++) {
                int cnt = 0;
                for (int j = 0; j < n; j++)
                    if ((i >> j) & 1) cnt += 1;
                if (cnt != len) continue;
                for (int cur = 0; cur < n; cur++) {
                    if (!((i >> cur) & 1)) continue;
                    int pre = i - (1 << cur);
                    int x = 1 + (k * (len - 1));
                    int need = strength[cur] - x * (len != 1);
                    int time = (need > 0 ? (need / x + ((need % x) != 0)) : 0) + 1;
                    f[i] = min(f[i], f[pre] + time);
                }
            }
        }
        return f[(1 << n) - 1] - 1;
    }
};

這也是一種 DP 的套路題目，我們可以稱他為 bit-dp

如果對於這種 bottom-up 的 DP 沒辦法理解的話，你可以考慮使用 top-down 的方式來解出這題，使用 top-down 就是我們先有一個遞迴的函數，他可以找出所有的排列順序，也就是假設現在有 3 個關卡，我們可以透過遞迴找到 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]，這 6 種的排列方式。之後再根據這樣的順序找到最小花費的時間作為答案。