大家好，我是晴天學長，很久很久沒有寫算法題解了，今天開始轉python了。💪💪💪
1）統計打字方案數
給你一個長度為 n 的整數數組 nums 和一個二維數組 queries ，其中 queries[i] = [li, ri, vali]。
每個 queries[i] 表示以下操作在 nums 上執行：
從數組 nums 中選擇范圍 [li, ri] 內的一個下標子集。 將每個選中下標處的值減去 正好 vali。
零數組 是指所有元素都等于 0 的數組。
返回使得經過前 k 個查詢（按順序執行）后，nums 轉變為 零數組 的最小可能 非負 值 k。如果不存在這樣的 k，返回 -1。
數組的 子集 是指從數組中選擇的一些元素（可能為空）。
示例 1：
輸入： nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]
輸出： 2
解釋：
對于查詢 0 （l = 0, r = 2, val = 1）：
將下標 [0, 2] 的值減 1。
數組變為 [1, 0, 1]。
對于查詢 1 （l = 0, r = 2, val = 1）：
將下標 [0, 2] 的值減 1。
數組變為 [0, 0, 0]，這就是一個零數組。因此，最小的 k 值為 2。
示例 2：
輸入： nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]
輸出： -1
解釋：
即使執行完所有查詢，也無法使 nums 變為零數組。
示例 3：
輸入： nums = [1,2,3,2,1], queries = [[0,1,1],[1,2,1],[2,3,2],[3,4,1],[4,4,1]]
輸出： 4
解釋：
對于查詢 0 （l = 0, r = 1, val = 1）：
將下標 [0, 1] 的值減 1。
數組變為 [0, 1, 3, 2, 1]。
對于查詢 1 （l = 1, r = 2, val = 1）：
將下標 [1, 2] 的值減 1。
數組變為 [0, 0, 2, 2, 1]。
對于查詢 2 （l = 2, r = 3, val = 2）：
將下標 [2, 3] 的值減 2。
數組變為 [0, 0, 0, 0, 1]。
對于查詢 3 （l = 3, r = 4, val = 1）：
將下標 4 的值減 1。
數組變為 [0, 0, 0, 0, 0]。因此，最小的 k 值為 4。
示例 4：
輸入： nums = [1,2,3,2,6], queries = [[0,1,1],[0,2,1],[1,4,2],[4,4,4],[3,4,1],[4,4,5]]
輸出： 4
提示：
1 <= nums.length <= 10
0 <= nums[i] <= 1000
1 <= queries.length <= 1000
queries[i] = [li, ri, vali]
0 <= li <= ri < nums.length
1 <= vali <= 10
2) .算法思路
我們首先注意到nums長度最長才只有10，我們可以枚舉每一個詢問，處理出一個arr[i]，arr[i]也是一個數組，代表了的位置i有哪些詢問可以使用，并且是有序的。然后對于每一個詢問可以處理的位置，加到對應的位置的數組中即可。
然后對于每一個位置，就是判斷選擇這些詢問，是否能夠湊出這個位置的值，并且是在用到的詢問最小的情況下，那么這就是01背包，對每一個位置我們都求一個01背包，定義f[i][j]代表了前i個詢問是否能夠湊出j。然后對于每一個位置求出的最少詢問數求最大值。
需要注意的是，這道題如果num所有元素為0的時候，是直接返回0，需要判斷一下，有點坑。
3) .算法步驟
1.創建一個二維數組arr，用于記錄每個點能夠被哪些區間覆蓋。對于每個查詢，遍歷區間中的點，將該點與對應的查詢值存儲在arr中。
2.對于每個點，遍歷其覆蓋的區間，使用動態規劃來嘗試湊出該點的值。定義一個二維數組f，其中f[i][j]表示在考慮前i個區間的情況下，是否可以湊出值為j。
3.初始化f[0][0] = True，表示不選取任何區間時，可以湊出值為0。
4.對于每個區間，考慮選取或不選取該區間。如果選取該區間，則需要判斷是否可以湊出值為j - arr[k][i][1]。
5.如果最終在考慮完所有區間后，可以湊出該點的值，則記錄下使用的區間索引，并更新cur的值。
6.最終返回mx + 1，其中mx表示使用的區間索引的最大值。
4）.代碼示例
class Solution:def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:if max(nums) == 0:return 0n = len(nums)m = len(queries)arr = [[] for _ in range(n)]#每個點能夠被哪一些區間覆蓋for i in range(m):l, r, val = queries[i]for j in range(l, r + 1):arr[j].append((i, val))#對于每一個點，問題轉換為了在盡量少用的情況下，湊出nums[i]mx = -inffor k,x in enumerate(nums):f = [[False] * (x + 1) for _ in range(len(arr[k]) + 1)]f[0][0] = Truecur = inffor i in range(len(arr[k])):for j in range(x + 1):#不選f[i + 1][j] = f[i][j]#選if j - arr[k][i][1] >= 0:f[i + 1][j] |= f[i][j - arr[k][i][1]] if f[i + 1][x]:cur = min(cur,arr[k][i][0])breakelse:return -1mx = max(mx,cur)return mx + 1
5）.總結
這個算法主要是通過動態規劃來解決問題。首先，對于每個點，算法找出它能夠被哪些區間覆蓋。然后，問題轉化為對于每個點，如何在盡量少的情況下湊出該點的值。
試題鏈接
