贮油卡车过沙漠问题用递推法

假设贮油卡车每次可以行驶 $m$ 公里，沙漠长度为 $n$ 公里，需要将 $n$ 公里的沙漠分成若干个长度为 $m$ 的区间，每个区间内需要一个加油站，问最少需要几个加油站？

使用递推法，定义数组 $dp$，其中 $dp[i]$ 表示从起点到第 $i$ 公里需要的最少加油站数量。则有：

$$
dp[i] = \begin{cases}
0 & i=0 \\
\min_{j=0}^{i-1}dp[j]+1 & i>0, i-j \leq m
\end{cases}
$$

其中，当 $i=0$ 时，不需要加油站；当 $i>0$ 时，枚举上一个加油站位置 $j$，如果 $i-j \leq m$，则说明当前位置可以通过上一个加油站到达，因此需要在 $dp[j]$ 的基础上加上一个加油站，即 $dp[i]=dp[j]+1$，取所有可能的 $dp[j]$ 的最小值。

最终答案为 $dp[n]$。

时间复杂度为 $O(n^2)$，可以使用滚动数组将空间复杂度优化为 $O(m)$。