[LeetCode 1094] 差分数组的本质是动态规划

差分数组其实就是动态规划的一个变体，因为对区间的修改最终还是会落实到每一个元素上。而且，这种修改一般是完全相同的，所以差分数组实际上是对状态修改进行了合并，从而优化了动态规划中 DP 数组的修改开销。

对于这道题来说，其实需要维护的就是在每一公里处车上的人数。并且，由于车是单向行驶的，当前的人数只依赖于上一公里时的人数，符合动态规划的模型。

朴素的想法是每次来一个区间，就遍历这个区间，但由于操作是相同的，可以对重复的操作进行合并，只保留头和尾即可。这也就是差分数组。

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001
        for num_passengers, fromi, toi in trips:
            diff[fromi] += num_passengers
            diff[toi + 1] -= num_passengers
        s = 0
        for n in diff:
            s += n
            if s > capacity:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12