leetcode983 每日一题：最低票价（动态规划）_983最低票价问题

题解

• 题目大意：
  • 旅游规划，给出数组days, days中的数据小于365，要求days给出的日期都能旅行，days中的日期是单调递增的。
  • 旅社有三种方案供选择，分别是1日游，7日游，30日游，三种价格记录在cost数组中，价格不一定从低到高
  • 输出：覆盖所有days的旅行最少需要多少钱
• 题解：
  • 不难发现，每个日期的价格取决于上一次价格的开销+这次的票价，因此是动态规划问题
  • 状态转移：
    • 当天旅行价格 = 上一次旅行+当前票价，因此状态转移方程就可以确定了, dp[i] = min(dp[i-day1], dp[i-day7], dp[i-day30])
    • 要注意的一点是，不在旅行状态的日期的花销等于最后一次旅行的花销，这里不能忘记更新。

class Solution {
   
    public int mincostTickets(int[] days, int[] costs) {
   
        final int N = 
1
2
3
4