总行驶距离

【模拟】按题意模拟，循环，主油箱超过5L且副油箱有油时，消耗5L油，然后用副油箱补主油箱，最后把主油箱里不足5L的油用完。

【数学】每次消耗5L主油箱的油就能得到1L的补充，相当于花4L油，假如mainTank是4的倍数则最后4L油得不到补充，所以应该是⌊(mainTank−1)/4⌋，算出总油量后，乘以 10 即可。

(资料图片仅供参考)

找出分区值

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

特别的排列

【状压DP-记忆化搜索实现】dfs(i,j)表示当前可以选的下标集合为i，上一个选的数的下标是j。转移：从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-递推实现】dfs改成f数组；递归改成循坏；递归边界改成f数组的初始值。

给墙壁刷油漆

【线性DP-记忆化搜索实现】选或不选的思路，如果付费刷第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-记忆化搜索实现】这是0-1背包的一种"至少装满"的变形。可以定义dfs(i,j)表示考虑前i个物品，剩余还需要凑出j的体积，此时的最小价值和。此时状态转移方程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-递推实现】改成递推。

关键词：