總行駛距離

【模擬】按題意模擬，循環(huán)，主油箱超過5L且副油箱有油時，消耗5L油，然后用副油箱補主油箱，最后把主油箱里不足5L的油用完。

【數(shù)學】每次消耗5L主油箱的油就能得到1L的補充，相當于花4L油，假如mainTank是4的倍數(shù)則最后4L油得不到補充，所以應該是?(mainTank?1)/4?，算出總油量后，乘以 10 即可。

找出分區(qū)值

【排序】排序后，序列中相鄰元素差值的最小值就是答案。

特別的排列

【狀壓DP-記憶化搜索實現(xiàn)】dfs(i,j)表示當前可以選的下標集合為i，上一個選的數(shù)的下標是j。轉(zhuǎn)移：從i中選一個下標k，如果nums[j] % nums[k] == 0 or nums[k] % nums[j] == 0，dfs(i,j) = sum(dfs(i \ {k}, k) for k in i)。遞歸邊界：dfs(0, j) = 1，dfs(U \ {i}, i)，U = {0,1,2,3,4,...,n-1}，答案是sum(dfs(U \ {i}, i) for i in range(n))。

【狀壓DP-遞推實現(xiàn)】dfs改成f數(shù)組；遞歸改成循壞；遞歸邊界改成f數(shù)組的初始值。

給墻壁刷油漆

【線性DP-記憶化搜索實現(xiàn)】選或不選的思路，如果付費刷第n-1堵墻，那么問題變成刷前n-2堵墻，付費時間和為time[n-1]，免費時間和0的最小開銷；如果免費刷第n-1堵墻，那么問題變成：刷前n-2堵墻，且付費時間和為0，免費時間和為1的最少開銷。定義dfs(i,j)為刷前i堵墻，j為付費時間和減去免費時間和。如果付費刷第i堵墻：dfs(i,j)=dfs(i-1, j+time[i]) + cost[i]。如果免費刷第i堵墻：dfs(i,j) = dfs(i-1,j-1)。兩種情況取最小值，dfs(i,j)=min(dfs(i-1, j+time[i]) + cost[i], dfs(i-1,j-1))，遞歸邊界：如果j>i，剩余的墻都可以免費刷，即dfs(i,j)=0，否則dfs(-1,j)=inf。遞歸入口dfs(n-1,0)。

【0-1背包DP-記憶化搜索實現(xiàn)】這是0-1背包的一種"至少裝滿"的變形。可以定義dfs(i,j)表示考慮前i個物品，剩余還需要湊出j的體積，此時的最小價值和。此時狀態(tài)轉(zhuǎn)移方程dfs(i,j)=min(dfs(i-1, j - time[i] - 1) + cost[i], dfs(i-1,j))。遞歸邊界：如果j≤0，那么不需要再選任何物品了，返回0；如果i<0，返回無窮大。 遞歸入口：dfs(n-1,n)，表示體積和至少為n，這正是我們要計算的。

【0-1背包DP-遞推實現(xiàn)】改成遞推。