一、题目描述
题目链接：https://leetcode-cn.com/problems/minimum-cost-for-tickets/
二、题目分析
这类型的题最直接的思路就是列举所有情况，自然就想到了dfs，而再这个过程中一般可以使用一个memo来进行优化。
我们使用memo[i]来记录，i表示从第i天开始旅游需要花费的最小钱数。我们使用ticketDP(int i)进行递归，i代表从第i天开始旅游，若memo[i]存在，则说明计算过了，直接返回，如果没有，我们就遍历1，7，30天车票的钱数，加上ticketDP（i+7）【这里我们以挑了7天的车票为例】。递归下去事实上就是自底向上的dp。
三、题目
class Solution { private int[] days; private int[] costs; private Integer[] memo; private int[] duration = {1,7,30}; public int mincostTickets(int[] days, int[] costs) { this.days = days; this.costs = costs; memo = new Integer[days.length]; return ticketDP(0); } private int ticketDP(int i) { if (i >= days.length) return 0; if (memo[i] != null) return memo[i]; int j = i; memo[i] = Integer.MAX_VALUE; for (int k = 0; k < 3; k ++ ) { while (j < days.length && days[j] < days[i] + duration[k]) { j++; } memo[i] = Math.min(memo[i],ticketDP(j) + costs[k]); } return memo[i]; } }
