# Leetcode 983. Minimum Cost For Tickets
###### tags: `leetcode` `daily`

[題目連結](https://leetcode.com/problems/minimum-cost-for-tickets/)

# Method DP
:::info
:bulb: **作法講解**:
We can use DP algorithm to solve this problem.

Definition:
`dp[i] = x` it means i-th day need x dollars.

State Transition Equation:
`dp[i] = dp[i - 1] + costs[0]`
`dp[i] = dp[i - 7] + costs[1]`
`dp[i] = dp[i - 30] + costs[2]`

:::

TC: O(N) SC: O(N)
完整程式碼

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        int idx = 0;
        vector<int> dp(366, INT32_MAX);

        dp[0] = 0;
        for(int i = 1 ; i <= 365 ; i++) {
            if((idx == n) || (i < days[idx])) {
                dp[i] = dp[i-1];
                continue;
            }

            dp[i] = dp[i-1] + costs[0];
            dp[i] = min(dp[i], dp[max(0, i - 7)] + costs[1]);
            dp[i] = min(dp[i], dp[max(0, i - 30)] + costs[2]);
            idx++;
        }
        return dp[365];
    }
};