update 1994.md

coderhare · coderhare · commit 0d22d95f7ce1 · 2022-02-22T16:27:25.000+08:00
diff --git a/leetcode/state_reduction/1986.md b/leetcode/state_reduction/1986.md
@@ -0,0 +1,30 @@
+首先见数据范围猜状压，其次，它的转移与数选择的先后有关，我们可以枚举每一个状态，
+从后往前遍历自己，寻找每个状态对应的最优解组合是否最优，这种遍历是`O(3 ^n)`,证明见二项式定理
+此外还有另一种遍历方式，需要开另一个记录数组，麻烦点.时间复杂度是`O(n * 2^n)`
+```c++
+class Solution {
+public:
+    int minSessions(vector<int>& a, int b) {
+        int n = a.size();
+        vector <int> f(1 << n, 1 << 29); f[0] = 0;
+        for(int i = 0; i < (1 << n); i++){
+            int mask = i, t = 0, idx = 0, s = 0;
+            while(mask){
+                if(mask & 1) t += a[idx];
+                if(t == b) t = 0, s++;
+                if(t > b) {
+                    s++;
+                    t = a[idx];
+                }
+                mask >>= 1;
+                idx++;
+            }
+            f[i] = s + (t > 0);
+            for(int j = i; j; j = (j - 1) & i){
+                f[i] = min(f[i], f[j ^ i] + f[j]);
+            }
+        }
+        return f.back();
+    }
+};
+```
