力扣983最低票价 - 一维DP - 值域爬楼梯与二分优化

983. 最低票价
这题可以看成「爬楼梯」题目的变种。
有两种思考角度，每种角度有两种写法。

角度一

我们从旅游的第一天i ii开始思考，n nn为旅行的最后一天，寻找子问题，分类讨论：

• 在第i ii天购买1 11天的车票，接下来要解决：从i + 1 i+1i+1到n nn天的最小花费
• 在第i ii天购买7 77天的车票，接下来要解决：从i + 7 i+7i+7到n nn天的最小花费
• 在第i ii天购买30 3030天的车票，接下来要解决：从i + 30 i+30i+30到n nn天的最小花费
  这和「爬楼梯」选择爬几层的思路很像。

写法一

本题数据范围很小，n ≤ 365 n≤365n≤365，故可以直接以自然日为下标，用动态规划在自然日上推进。
定义d f s ( i ) dfs(i)dfs(i)表示i ii到n nn天的最小花费。

• 若第i ii天不是旅游日，就有：
  d f s ( i ) = d f s ( i + 1 ) dfs(i) = dfs(i + 1)dfs(i)=dfs(i+1)
• 若第i ii天是旅游日，则有：
  d f s ( i ) = m i n ( d f s ( i + 1 ) + c o s t s [ 0 ] , d f s ( i + 7 ) + c o s t s [ 1 ] , d f s ( i + 30 ) + c o s t s [ 2 ] ) dfs(i) = min(dfs(i+1)+costs[0], dfs(i+7)+costs[1], dfs(i+30)+costs[2])dfs(i)=min(dfs(i+1)+costs[0],dfs(i+7)+costs[1],dfs(i+30)+costs[2])
• 递归边界：当i > n i>ni>n时d f s ( i ) = 0 dfs(i)=0dfs(i)=0，此时没有要旅行的天数
• 递归入口：d f s ( D f i r s t ) dfs(D_{first})dfs(Dfirst​)，其中D f i r s t D_{first}Dfirst​为旅行的第一天
  当然也可以直接把旅行第一天定为1 11，最后一天定为365 365365。

加上记忆化就有：

classSolution{boolean[]vis=newboolean[366];int[]cache=newint[366];int[]costs;publicintmincostTickets(int[]days,int[]costs){this.costs=costs;for(intx:days)vis[x]=true;Arrays.fill(cache,-1);returndfs(1);}privateintdfs(inti){if(i>365)return0;if(cache[i]!=-1)returncache[i];if(vis[i]!=true)returncache[i]=dfs(i+1);intc1=dfs(i+1)+costs[0];intc2=dfs(i+7)+costs[1];intc3=dfs(i+30)+costs[2];intres=Math.min(c1,Math.min(c2,c3));cache[i]=res;returnres;}}

时间复杂度：O ( 365 ) O(365)O(365)或O ( D l a s t − D f i r s t ) O(D_{last}-D_{first})O(Dlast​−Dfirst​)。
空间复杂度：O ( 365 ) O(365)O(365)或O ( D l a s t − D f i r s t ) O(D_{last}-D_{first})O(Dlast​−Dfirst​)。

递推形式：

classSolution{boolean[]vis=newboolean[366];publicintmincostTickets(int[]days,int[]costs){for(intx:days)vis[x]=true;int[]f=newint[370];f[366]=0;for(inti=365;i>=1;i--){if(vis[i]!=true){f[i]=f[i+1];continue;}intc1=f[Math.min(i+1,366)]+costs[0];intc2=f[Math.min(i+7,366)]+costs[1];intc3=f[Math.min(i+30,366)]+costs[2];f[i]=Math.min(c1,Math.min(c2,c3));}returnf[1];}}

写法二

当d a y s [ i ] days[i]days[i]比较大时，比如≤ 1 0 9 ≤10^{9}≤109时，上面以值域推进的做法就不行了。
此时用日期索引上做「跳跃」，就能解决复杂度与d a y s [ i ] days[i]days[i]值域有关的问题了。

大体思路是一样的，我们定义d f s ( i ) dfs(i)dfs(i)为第d a y s [ i ] days[i]days[i]天到第d a y s [ d a y s . l e n g t h − 1 ] days[days.length-1]days[days.length−1]的旅行最小花费。只需要在「跳跃」时，跳跃到第一个≥ d a y s [ i ] + ( 1 , 7 , 30 ) ≥days[i]+(1,7,30)≥days[i]+(1,7,30)的索引j jj就行，这可以用二分优化。

记忆化搜索：

classSolution{int[]cache,costs,days;intn;publicintmincostTickets(int[]days,int[]costs){this.costs=costs;this.n=days.length;this.days=days;cache=newint[n+10];Arrays.fill(cache,-1);returndfs(0);}privateintdfs(inti){if(i>=n)return0;if(cache[i]!=-1)returncache[i];intc1=dfs(lowerBound(i,1))+costs[0];intc2=dfs(lowerBound(i,7))+costs[1];intc3=dfs(lowerBound(i,30))+costs[2];intres=Math.min(c1,Math.min(c2,c3));cache[i]=res;returnres;}// 左闭右开privateintlowerBound(inti,intday){intl=i+1,r=n;while(l<r){intmid=l+r>>1;if(days[mid]>=days[i]+day)r=mid;elsel=mid+1;}returnr;}}

时间复杂度：O ( n l o g n ) O(nlogn)O(nlogn)，其中n nn为d a y s daysdays的长度。
空间复杂度：O ( n ) O(n)O(n)。

角度二

上面我们是从第一天开始入题，从左往右思考。我们也可以从右往左思考。
我们从旅游的最后一天i ii开始思考，寻找子问题，分类讨论：

• 在第i ii天购买1 11天的车票，接下来要解决：从1 11到i − 1 i-1i−1天的最小花费
• 在第i − 7 + 1 i-7+1i−7+1天购买7 77天的车票，接下来要解决：从1 11到i − 7 i-7i−7天的最小花费
• 在第i − 30 + 1 i-30+1i−30+1天购买30 3030天的车票，接下来要解决：从1 11到i − 30 i-30i−30天的最小花费
  这种方法更方便把递归翻译成递推。

定义d f s ( i ) dfs(i)dfs(i)为第1 11到i ii天的最小花费，后续思考大同小异，不再赘述。给出以值域推进的代码：

classSolution{boolean[]vis=newboolean[366];int[]cache=newint[366];int[]costs;publicintmincostTickets(int[]days,int[]costs){this.costs=costs;for(intx:days)vis[x]=true;Arrays.fill(cache,-1);returndfs(365);}privateintdfs(inti){if(i<=0)return0;if(cache[i]!=-1)returncache[i];if(vis[i]!=true)returncache[i]=dfs(i-1);intc1=dfs(i-1)+costs[0];intc2=dfs(i-7)+costs[1];intc3=dfs(i-30)+costs[2];intres=Math.min(c1,Math.min(c2,c3));cache[i]=res;returnres;}}

#solutions