diff options
author | Jack Sangdahl <[email protected]> | 2024-12-31 08:09:13 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-31 08:09:13 +0100 |
commit | aeac76f37b44fe79a23411fcd6e3e8ea79a2b5df (patch) | |
tree | 91a7d882534372e555afec208a1d5a4e4d6b71fb | |
parent | e8c6049f79e0102afa0917cca08062232d465650 (diff) | |
download | leetcode-aeac76f37b44fe79a23411fcd6e3e8ea79a2b5df.tar.gz leetcode-aeac76f37b44fe79a23411fcd6e3e8ea79a2b5df.zip |
983. minimum cost for tickets
-rw-r--r-- | min_cost_ticket.c | 54 | ||||
-rw-r--r-- | min_cost_ticket.py | 42 |
2 files changed, 61 insertions, 35 deletions
diff --git a/min_cost_ticket.c b/min_cost_ticket.c index 88abdb2..610610f 100644 --- a/min_cost_ticket.c +++ b/min_cost_ticket.c @@ -1,7 +1,5 @@ // 983. Minimum Cost For Tickets -#include <stdbool.h> -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * you have planned some train traveling one year in advance. the days of the @@ -13,42 +11,28 @@ * day in the given list of days. */ -#define MIN(a, b, c) \ - ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c))) - -bool find_item(int *days, int days_size, int target) { - int left = 0, right = days_size - 1, mid; - while (left <= right) { - mid = (left + right) / 2; - if (days[mid] == target) - return true; - if (days[mid] > target) - right = mid - 1; - else - left = mid + 1; - } - return false; -} - -int mincostTickets(int *days, int days_size, int *costs, int costs_size) { - int arr_size = days[days_size - 1] + 30; - int *dp = calloc(arr_size, sizeof(int)); - for (int i = 30; i < arr_size; i++) { - if (find_item(days, days_size, i - 29) == false) +int mincostTickets(int *days, int daysSize, int *costs, int costsSize) { + int dp[366] = {0}, idx = 0; + for (int i = 1; i <= 365; ++i) + if (idx < daysSize && i == days[idx]) { + int one = dp[i - 1] + costs[0]; + int seven = dp[i - 7 > 0 ? i - 7 : 0] + costs[1]; + int thirty = dp[i - 30 > 0 ? i - 30 : 0] + costs[2]; + dp[i] = one < seven ? one < thirty ? one : thirty + : seven < thirty ? seven + : thirty; + ++idx; + } else dp[i] = dp[i - 1]; - else - dp[i] = MIN(dp[i - 1] + costs[0], dp[i - 7] + costs[i], - dp[i - 30] + costs[2]); - } - int ans = dp[arr_size - 1]; - free(dp); - return ans; + return dp[365]; } int main() { int d1[] = {1, 4, 6, 7, 8, 20}, d2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31}; - int c1[] = {2, 7, 15}; - printf("%d\n", mincostTickets(d1, 6, c1, 3)); // expect: 11 - printf("%d\n", mincostTickets(d2, 12, c1, 3)); // expect: 11 + int c1[] = {2, 7, 15}, c2[] = {2, 7, 15}; + printf("%d\n", + mincostTickets(d1, ARRAY_SIZE(d1), c1, ARRAY_SIZE(c1))); // expect: 11 + printf("%d\n", + mincostTickets(d2, ARRAY_SIZE(d2), c1, ARRAY_SIZE(c2))); // expect: 17 } diff --git a/min_cost_ticket.py b/min_cost_ticket.py new file mode 100644 index 0000000..02c00c1 --- /dev/null +++ b/min_cost_ticket.py @@ -0,0 +1,42 @@ +# 983. Minimum Cost For Tickets + +""" +you have planned some train traveling one year in advance. the days of the +year in which you will travel are given as an integer array 'days'. each day +is an integer 1 - 365. train tickets are sold in three different ways: 1 day +pass sold for 'costs[0]' dollars 7 day pass sold for 'costs[1]' dollars 30 +day pass sold for 'costs[2]' dollars the passes allow that many days of +consecutive travel. return mininum number of dollars you need to travel every +day in the given list of days. +""" + + +class Solution(object): + def mincostTickets(self, days, costs): + """ + :type days: List[int] + :type costs: List[int] + :rtype: int + """ + dp = [0 for i in range(days[-1] + 1)] + dy = set(days) + for i in range(days[-1] + 1): + if i not in dy: + dp[i] = dp[i - 1] + else: + dp[i] = min( + dp[max(0, i - 7)] + costs[1], + dp[max(0, i - 1)] + costs[0], + dp[max(0, i - 30)] + costs[2], + ) + return dp[-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.mincostTickets(days=[1, 4, 6, 7, 8, 20], costs=[2, 7, 15])) + print( + obj.mincostTickets( + days=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], costs=[2, 7, 15] + ) + ) |