【力扣 中等 C】983. 最低票价

目录

题目

解法一：一维dp

题目

待添加

解法一：一维dp

int min(int a, int b)
{return a < b ? a : b;
}int find(const int* nums, int start, int end, int target)
{int left = start, right = end;int index = end + 1;while (left <= right){int mid = (left + right) / 2;if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target){index = mid;right = mid - 1;}elsereturn mid;}return index;
}int compute(const int* days, int size1, const int* costs, int size2)
{const int cDays[3] = {1, 7, 30};int* dp = malloc(sizeof(*dp) * (size1 + 1));for (int i = 0; i < size1; i++)dp[i] = INT_MAX;dp[size1] = 0;for (int i = size1 - 1; i >= 0; i--)for (int j = 0; j < 3; j++){int nextIndex = find(days, i, size1 - 1, days[i] + cDays[j]);dp[i] = min(dp[i], costs[j] + dp[nextIndex]);}int minCharge = dp[0];free(dp);return minCharge;
}int mincostTickets(int* days, int daysSize, int* costs, int costsSize)
{return compute(days, daysSize, costs, costsSize);
}