[数据结构与算法]leetcode282周赛T4（需要加性质的DP）

DFS分析

• naive思路：在每个结点选择轮胎。
• 但只要发生改变，如果深度相同，只需要记录当前深度往下的搜索结果即可。（记忆化搜索）
• 从该节点回溯到第一个连续的轮胎，该轮胎的使用一定是同样步骤中耗费最小的。

最优子结构

• 第一个轮胎选择后连续使用到第j场，则j+1场到最后时间也是最优
• 令dp[i]，完成i后缀的比赛所用时间最小值，则考虑肯定更换轮胎的时间(暂且不考虑边界情况)
  d p [ i ] = m i n P 轮 胎 ， j 步 { d p [ i + j ] + c h a n g e T i m e + P 轮 胎 使 用 j 步 的 最 小 时 间 } dp[i] = min_{P轮胎，j步}\{dp[i+j] + changeTime + P轮胎使用j步的最小时间\} dp[i]=minP轮胎，j步?{dp[i+j]+changeTime+P轮胎使用j步的最小时间}
• j有上界。这是因为同一个轮胎，当$f{r}^{x?1}>=changetime+f$肯定要更换轮胎。
• 没有考虑到的点：提前预处理求最小值。
• 总结：使用DP时，要注意拆解的小部分是否是原先问题的子问题。例如此题更换轮胎剩下的部分就是子问题，而仅仅确定第一个轮胎后后续的并不是子问题。其次把DP方程写下，别空想。并且预处理。

实现

class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        int pre[21];
        for(int i = 0;i<21;i++)
            pre[i] = 1e10;
        for(int  i = 0;i<tires.size();i++)
        {
            int f = tires[i][0];
            int r = tires[i][1];
            int ret;
            int co = 1;
            int sum = 0;
            while(co <= 20)
            {
                ret = f;
                sum+=ret;
                while(co <= 20 && ret < f + changeTime)
                {
                    pre[co] = min(pre[co],sum);
                    ret *= r;
                    if(ret < f + changeTime)
                        sum += ret;
                    co++;
                }
                if(co <= 20)
                    sum += changeTime;
            }
        }
        int dp[numLaps];
        dp[numLaps - 1] = pre[1];
        for(int i = numLaps  -2;i>=0;i--)
        {
            dp[i] = 1e10;
            for(int j = i + 1 ; j - i <= 20 && j <= numLaps;j++)
            {
                if(j < numLaps)
                {
                    dp[i] = min(dp[i],dp[j] + changeTime + pre[j - i]);
                }
                else
                    dp[i] = min(dp[i],pre[j - i]);
            }
        }
        return dp[0];
    }
};