aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-31 08:09:13 +0100
committerJack Sangdahl <[email protected]>2024-12-31 08:09:13 +0100
commitaeac76f37b44fe79a23411fcd6e3e8ea79a2b5df (patch)
tree91a7d882534372e555afec208a1d5a4e4d6b71fb
parente8c6049f79e0102afa0917cca08062232d465650 (diff)
downloadleetcode-aeac76f37b44fe79a23411fcd6e3e8ea79a2b5df.tar.gz
leetcode-aeac76f37b44fe79a23411fcd6e3e8ea79a2b5df.zip
983. minimum cost for tickets
-rw-r--r--min_cost_ticket.c54
-rw-r--r--min_cost_ticket.py42
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]
+ )
+ )