刷墙最少开销：动态规划解法详解

本文探讨了如何使用动态规划解决刷墙最少开销问题。假设给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：/n/n一位需要付费的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。/n一位免费的油漆匠，刷任意一堵墙的时间为 1 单位，开销为 0。但是必须在付费油漆匠工作时，免费油漆匠才会工作。/n/n问题： 请你返回刷完 n 堵墙最少开销为多少。/n/n思路：动态规划/n/n首先考虑只有一名付费油漆匠的情况。定义状态 $f(i,j)$ 表示前 $i$ 堵墙，花费了 $j$ 的时间，最小的开销为多少。对于每一堵墙都有两种选择：让付费油漆匠刷或让免费油漆匠刷。因此可以得到状态转移方程：/n/n$$f(i,j)=/min /{f(i-1,j-time[i])+cost[i],/ f(i-1,j-1)/}$$ /n/n其中第一项表示让付费油漆匠刷第 $i$ 堵墙，第二项表示让免费油漆匠刷第 $i$ 堵墙，因此需要在第 $i-1$ 堵墙的基础上加上相应的时间和开销。/n/n当有两名油漆匠时，需要考虑两名油漆匠交替工作的情况。定义状态 $g(i,j)$ 表示前 $i$ 堵墙，花费了 $j$ 的时间，最小的开销为多少，其中最后一次工作是由付费油漆匠完成的。同样，对于每一堵墙都有两种选择：让付费油漆匠刷或让免费油漆匠刷。因此可以得到状态转移方程：/n/n$$g(i,j)=/min /{g(i-1,j-time[i])+cost[i],/ f(i-1,j-1)/}$$ /n/n其中第一项表示让付费油漆匠刷第 $i$ 墙，因此需要在第 $i-1$ 墙的基础上加上相应的时间和开销；第二项表示让免费油漆匠在第 $i-1$ 墙工作，等待付费油漆匠完成第 $i$ 墙的工作。/n/n最终的答案为 $/min/{f(n,j),/ g(n,j)/}$，其中 $j$ 表示完成 $n$ 墙的最少时间。时间复杂度为 $O(n^2)$。