1#include <stdio.h>
2
3int mincostTickets(int* days, int daysSize, int* costs, int costsSize) {
4    int n = days[daysSize - 1];
5    int dp[n + 1];
6    int dayIndex = 0;
7    for (int i = 0; i <= n; i++) dp[i] = 0;
8    for (int i = 1; i <= n; i++) {
9        if (i != days[dayIndex]) {
10            dp[i] = dp[i - 1];
11        } else {
12            int oneDayPass = dp[i - 1] + costs[0];
13            int sevenDayPass = dp[(i - 7 >= 0) ? i - 7 : 0] + costs[1];
14            int thirtyDayPass = dp[(i - 30 >= 0) ? i - 30 : 0] + costs[2];
15            dp[i] = oneDayPass < sevenDayPass ? oneDayPass : sevenDayPass;
16            dp[i] = dp[i] < thirtyDayPass ? dp[i] : thirtyDayPass;
17            dayIndex++;
18        }
19    }
20    return dp[n];
21}
22
23int main() {
24    int days[] = {1, 4, 6, 7, 8, 20};
25    int costs[] = {2, 7, 15};
26    int result = mincostTickets(days, 6, costs, 3);
27    printf("The minimum cost to travel is %d\n", result);
28    return 0;
29}

1using System;
using System.Collections.Generic;

public class Solution {
    private int[] days;
    private int[] costs;
    private int[] memo;

    public int MincostTickets(int[] days, int[] costs) {
        this.days = days;
        this.costs = costs;
        this.memo = new int[days.Length];
        Array.Fill(memo, -1);
        return Dfs(0);
    }

    private int Dfs(int i) {
        if (i >= days.Length) return 0;
        if (memo[i] != -1) return memo[i];

        int oneDay = costs[0] + Dfs(i + 1);
        int j = i;
        while (j < days.Length && days[j] < days[i] + 7) j++;
        int sevenDay = costs[1] + Dfs(j);
        while (j < days.Length && days[j] < days[i] + 30) j++;
        int thirtyDay = costs[2] + Dfs(j);

        return memo[i] = Math.Min(oneDay, Math.Min(sevenDay, thirtyDay));
    }
}