https://leetcode.com/problems/minimum-time-to-finish-the-race/
很好的题干，对dp的灵活运用。

个人解答

  1. class Solution:
  2.     def minimumFinishTime(self, ts: List[List[int]], c: int, n: int) -> int:
  3.         dp = [math.inf] * n
  4.         for f, r in ts:
  5.             acc = f
  6.             for i in range(min(n, 17)):
  7.                 dp[i] = min(dp[i], acc)
  8.                 acc = acc * r + f
  9.         for i in range(1, n):
  10.             for j in range(i):
  11.                 dp[i] = min(dp[i], dp[j] + c + dp[i - j - 1])
  12.         return dp[-1]

题目分析

题目是个很实际的问题，对于换胎时间和轮胎损耗的优化问题。
其实这道题的dp转移公式是比较明确的，把k圈分解成m圈加上k-m圈以及换胎时间。
但是反而是初始条件，有点难受，当时没想出来。
现在回过头来看，其实是很直接的，不换胎的时间，就是初始条件，不用考虑换胎时间和增加后的时间之间的大小关系，初始条件都是不换胎的，之后dp的转移关系会保证这一点。

于是，定好初始条件之后，两重遍历确定即可，如题解所示。