Open seungriyou opened 5 months ago
https://leetcode.com/problems/minimum-cost-for-tickets/ similar to #71
다음과 같이 dp table을 기록한다.
dp[i]: i일까지 확인했을 때의 ticket의 min cost
day를 1일부터 days[-1](max day)까지 순회하며,
day
1
days[-1]
max(..., 0)을 하는 것은 negative index를 방지하기 위함이다.
max(..., 0)
dp[day] = min( dp[max(day - 30, 0)] + costs[2], dp[max(day - 7, 0)] + costs[1], dp[max(day - 1, 0)] + costs[0] )
day - 1
O(max(days))
O(366)
Approach
다음과 같이 dp table을 기록한다.
day를1일부터days[-1](max day)까지 순회하며,day가 travel day에 속한다면, 다음의 값으로 저장한다.day가 travel day에 속하지 않는다면, 1일 전(=day - 1)의 값을 그대로 저장한다.Complexity
O(max(days))O(max(days))(=O(366))