# Lowest Cost Shirt Sequence ## Solution 1: Top-Down Dynamic Programming with Memoization ### Intuition The problem asks for a sequence of choices over several days to achieve a minimum total cost, with each choice affecting future options. This structure suggests a dynamic programming or recursive approach. A natural way to think about this is recursively. The minimum cost for `n` days is the cost of a shirt today plus the minimum cost for the remaining `n-1` days. The choice for today's shirt color is constrained by yesterday's color. We can define a function, say `min_cost(day, previous_color)`, that calculates the minimum cost from the current `day` to the end. Calling this function repeatedly would lead to re-calculating the same subproblems (e.g., finding the minimum cost from day 5 onwards, having chosen blue on day 4). To avoid this redundant work, we can store the result of each subproblem in a cache or "memoization" table. Once we have the minimum costs computed and stored, we need to find the actual sequence of shirts. We can do this by starting from day 0 and re-tracing the decisions that led to the overall minimum cost, using our memoization table to guide us at each step. ### Approach - Define a recursive function that takes the current `day` and the `previous_color_index` as parameters. - Use a 2D array, `memo`, as a cache to store the results of subproblems, initialized to a value indicating they haven't been computed yet. - The base case for the recursion is when the `day` equals `n` (the total number of days), in which case the cost is 0. - In the recursive step, iterate through the three possible colors for the current `day`. If a color is different from the `previous_color_index`, calculate the potential total cost by adding the current shirt's cost to the result of a recursive call for the next day. - The function returns the minimum of these potential costs, storing it in the `memo` table before returning. - After the initial recursive call populates the `memo` table, reconstruct the path. Start from day 0, and at each day, determine which color choice leads to the known minimum cost for the remaining days, using the `memo` table. - Append the chosen color to the result sequence and proceed to the next day with the updated state. ### Pseudocode ```pseudocode function lowest_cost(blue_costs, green_costs, red_costs) { n = length of blue_costs costs = a 2D array with [blue_costs, green_costs, red_costs] /* memo[day][prev_color_idx] stores min cost from 'day' onwards */ /* prev_color_idx: 0=b, 1=g, 2=r, 3=none (for day 0) */ memo = create a 2D array of size (n+1) x 4, initialized to -1 /* Start the recursion from day 0 with no previous color */ solve(0, 3, n, costs, memo) /* Reconstruct the path */ result = empty list of characters last_color_idx = 3 /* Sentinel for no previous color */ /* Iterate through each day to find the optimal color choice */ for day = 0 to n - 1 { min_cost = infinity best_color_idx = -1 /* Try each color for the current day */ for color_idx = 0 to 2 { /* Check if the color is valid (not same as last day's) */ if color_idx != last_color_idx { /* Calculate cost for this choice: current shirt + min future cost */ current_total_cost = costs[color_idx][day] + memo[day + 1][color_idx] /* If this choice is better, update our best choice for this day */ if current_total_cost < min_cost { min_cost = current_total_cost best_color_idx = color_idx } } } /* Add the best color to our result sequence */ if best_color_idx == 0 { add 'b' to result } else if best_color_idx == 1 { add 'g' to result } else { add 'r' to result } /* Update the last color for the next day's constraint */ last_color_idx = best_color_idx } /* Return the final sequence of colors */ return result } function solve(day, prev_color_idx, n, costs, memo) { /* Base case: If we are past the last day, cost is 0 */ if day == n { return 0 } /* If this subproblem is already solved, return the cached result */ if memo[day][prev_color_idx] != -1 { return memo[day][prev_color_idx] } min_cost = infinity /* Iterate through all possible colors for the current day */ for color_idx = 0 to 2 { /* Ensure we don't pick the same color as the previous day */ if color_idx != prev_color_idx { /* Recursively find the minimum cost for the rest of the days */ cost = costs[color_idx][day] + solve(day + 1, color_idx, n, costs, memo) min_cost = min(min_cost, cost) } } /* Cache the result and return it */ memo[day][prev_color_idx] = min_cost return min_cost } ``` ### Code Implementation **C++** ```cpp #include #include #include #include using namespace std; class solution { public: vector lowest_cost(const vector& blue_costs, const vector& green_costs, const vector& red_costs) { int n = blue_costs.size(); if (n == 0) { return {}; } vector> costs = {blue_costs, green_costs, red_costs}; vector> memo(n + 1, vector(4, -1)); solve(0, 3, n, costs, memo); vector result; int last_color_idx = 3; // 3 represents no previous color for (int day = 0; day < n; ++day) { long long min_path_cost = LLONG_MAX; int best_color_idx = -1; for (int color_idx = 0; color_idx < 3; ++color_idx) { if (color_idx != last_color_idx) { long long current_cost = costs[color_idx][day] + memo[day + 1][color_idx]; if (best_color_idx == -1 || current_cost < min_path_cost) { min_path_cost = current_cost; best_color_idx = color_idx; } } } if (best_color_idx == 0) result.push_back('b'); else if (best_color_idx == 1) result.push_back('g'); else result.push_back('r'); last_color_idx = best_color_idx; } return result; } private: long long solve(int day, int prev_color_idx, int n, const vector>& costs, vector>& memo) { if (day == n) { return 0; } if (memo[day][prev_color_idx] != -1) { return memo[day][prev_color_idx]; } long long min_cost = LLONG_MAX; for (int color_idx = 0; color_idx < 3; ++color_idx) { if (color_idx != prev_color_idx) { min_cost = min(min_cost, (long long)costs[color_idx][day] + solve(day + 1, color_idx, n, costs, memo)); } } return memo[day][prev_color_idx] = min_cost; } }; ``` **Python** ```python import sys sys.setrecursionlimit(200005) class solution: def lowest_cost(self, blue_costs, green_costs, red_costs): n = len(blue_costs) if n == 0: return [] costs = [blue_costs, green_costs, red_costs] memo = {} def solve(day, prev_color_idx): if day == n: return 0 if (day, prev_color_idx) in memo: return memo[(day, prev_color_idx)] min_cost = float('inf') for color_idx in range(3): if color_idx != prev_color_idx: cost = costs[color_idx][day] + solve(day + 1, color_idx) min_cost = min(min_cost, cost) memo[(day, prev_color_idx)] = min_cost return min_cost solve(0, -1) # -1 represents no previous color # Reconstruct path result = [] last_color_idx = -1 colors = ['b', 'g', 'r'] # Build a memoization table accessible by indices for reconstruction memo_for_path = [[-1] * 4 for _ in range(n + 1)] for i in range(n, -1, -1): for j in range(4): if i == n: memo_for_path[i][j] = 0 continue min_c = float('inf') for k in range(3): if k != j: min_c = min(min_c, costs[k][i] + memo_for_path[i+1][k]) memo_for_path[i][j] = min_c for day in range(n): min_path_cost = float('inf') best_color_idx = -1 for color_idx in range(3): if color_idx != last_color_idx: current_cost = costs[color_idx][day] + memo_for_path[day + 1][color_idx] if best_color_idx == -1 or current_cost < min_path_cost: min_path_cost = current_cost best_color_idx = color_idx result.append(colors[best_color_idx]) last_color_idx = best_color_idx return result ``` **Java** ```java import java.util.*; class Solution { private long[][] memo; private int[][] costs; private int n; public char[] lowest_cost(int[] blue_costs, int[] green_costs, int[] red_costs) { this.n = blue_costs.length; if (n == 0) { return new char[0]; } this.costs = new int[][]{blue_costs, green_costs, red_costs}; this.memo = new long[n + 1][4]; for (long[] row : memo) { Arrays.fill(row, -1); } solve(0, 3); // 3 represents no previous color char[] result = new char[n]; int last_color_idx = 3; for (int day = 0; day < n; ++day) { long min_path_cost = Long.MAX_VALUE; int best_color_idx = -1; for (int color_idx = 0; color_idx < 3; ++color_idx) { if (color_idx != last_color_idx) { long current_cost = (long)costs[color_idx][day] + memo[day + 1][color_idx]; if (best_color_idx == -1 || current_cost < min_path_cost) { min_path_cost = current_cost; best_color_idx = color_idx; } } } if (best_color_idx == 0) result[day] = 'b'; else if (best_color_idx == 1) result[day] = 'g'; else result[day] = 'r'; last_color_idx = best_color_idx; } return result; } private long solve(int day, int prev_color_idx) { if (day == n) { return 0; } if (memo[day][prev_color_idx] != -1) { return memo[day][prev_color_idx]; } long min_cost = Long.MAX_VALUE; for (int color_idx = 0; color_idx < 3; ++color_idx) { if (color_idx != prev_color_idx) { min_cost = Math.min(min_cost, (long)costs[color_idx][day] + solve(day + 1, color_idx)); } } return memo[day][prev_color_idx] = min_cost; } } ``` **JavaScript** ```javascript class Solution { static lowest_cost(blue_costs, green_costs, red_costs) { const n = blue_costs.length; if (n === 0) { return []; } const costs = [blue_costs, green_costs, red_costs]; const memo = new Map(); function solve(day, prev_color_idx) { if (day === n) { return 0; } const key = `${day},${prev_color_idx}`; if (memo.has(key)) { return memo.get(key); } let min_cost = Infinity; for (let color_idx = 0; color_idx < 3; ++color_idx) { if (color_idx !== prev_color_idx) { const cost = costs[color_idx][day] + solve(day + 1, color_idx); min_cost = Math.min(min_cost, cost); } } memo.set(key, min_cost); return min_cost; } solve(0, -1); // -1 for no previous color // Reconstruct path const result = []; let last_color_idx = -1; const colors = ['b', 'g', 'r']; for (let day = 0; day < n; ++day) { let min_path_cost = Infinity; let best_color_idx = -1; for (let color_idx = 0; color_idx < 3; ++color_idx) { if (color_idx !== last_color_idx) { const future_cost_key = `${day + 1},${color_idx}`; const future_cost = memo.has(future_cost_key) ? memo.get(future_cost_key) : 0; const current_cost = costs[color_idx][day] + future_cost; if (best_color_idx === -1 || current_cost < min_path_cost) { min_path_cost = current_cost; best_color_idx = color_idx; } } } result.push(colors[best_color_idx]); last_color_idx = best_color_idx; } return result; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n)` — The recursive function `solve` has `n * 4` possible states, each computed once. Path reconstruction is a single `O(n)` loop. - **Space Complexity:** `O(n)` — The memoization table uses `(n+1) x 4` space. Recursion stack uses `O(n)` in the worst case. --- ## Solution 2: Bottom-Up Dynamic Programming with Path Reconstruction ### Intuition Instead of starting from the first day and making choices forward (recursion), we can build our solution iteratively from day 0 up to day `n-1`. For any given day `i`, the minimum cost to arrive at this day with a certain color shirt depends only on the minimum costs from the previous day, `i-1`. We can maintain a table, let's call it `dp`, where `dp[i][color]` stores the minimum total cost of buying shirts for the first `i+1` days, with the shirt on day `i` being of a specific `color`. To calculate `dp[i][blue]`, we must have chosen either green or red on day `i-1`. We'd pick whichever of those resulted in a lower cost up to day `i-1`. So, `dp[i][blue]` would be `cost_of_blue_shirt_on_day_i + min(dp[i-1][green], dp[i-1][red])`. By filling this table day by day, we find the minimum costs for all possibilities. The final answer is the minimum of the three costs on the last day. To find the actual sequence of colors, we can work backward from the last day. We find which color gave the minimum cost on the last day, then look at the previous day to see which choice led to that optimal cost, and so on, until we reach the first day. ### Approach - Create a 2D `dp` table of size `n x 3`. `dp[i][j]` stores the minimum cost up to day `i` ending with color `j` (where `j=0` for blue, `1` for green, `2` for red). - Initialize the first row of the `dp` table with the costs of the shirts on day 0. - Iterate from day `i = 1` to `n-1`. In each iteration, calculate `dp[i][0]`, `dp[i][1]`, and `dp[i][2]` using the recurrence relations based on the values in `dp[i-1]`. - After the table is filled, find the minimum value in the last row (`dp[n-1]`) to determine the total minimum cost and the color of the shirt for the last day. - Start a backtracking process from day `n-1` down to day 0. - At each day `i`, given the chosen color for that day, determine the color for day `i-1` by checking which of the allowed previous colors' `dp` values, when added to the current day's shirt cost, equals the `dp` value of the current day's chosen color. - Store the sequence of colors found during backtracking. Since we are moving backward, the resulting sequence will be in reverse order. - Finally, reverse the sequence to get the correct order from day 0 to `n-1`. ### Pseudocode ```pseudocode function lowest_cost(blue_costs, green_costs, red_costs) { n = length of blue_costs if n == 0 { return empty list } /* dp[i][j] = min cost up to day i, ending with color j (0:b, 1:g, 2:r) */ dp = create a 2D array of size n x 3 /* Base case: Day 0 */ dp[0][0] = blue_costs[0] dp[0][1] = green_costs[0] dp[0][2] = red_costs[0] /* Fill the DP table for remaining days */ for i = 1 to n - 1 { /* Cost to end with blue on day i */ dp[i][0] = blue_costs[i] + min(dp[i-1][1], dp[i-1][2]) /* Cost to end with green on day i */ dp[i][1] = green_costs[i] + min(dp[i-1][0], dp[i-1][2]) /* Cost to end with red on day i */ dp[i][2] = red_costs[i] + min(dp[i-1][0], dp[i-1][1]) } /* --- Path Reconstruction --- */ result = empty list of characters of size n /* Find the color for the last day */ last_day_min_cost = min(dp[n-1][0], dp[n-1][1], dp[n-1][2]) last_color_idx = -1 if last_day_min_cost == dp[n-1][0] { last_color_idx = 0 } else if last_day_min_cost == dp[n-1][1] { last_color_idx = 1 } else { last_color_idx = 2 } /* Set the color for the last day in the result */ colors = ['b', 'g', 'r'] result[n-1] = colors[last_color_idx] /* Backtrack from the second to last day to the first day */ for i = n - 2 down to 0 { prev_color_idx = -1 /* Based on the color chosen for day i+1, find the color for day i */ if last_color_idx == 0 { /* Current was blue, previous must be green or red */ if dp[i+1][0] - blue_costs[i+1] == dp[i][1] { prev_color_idx = 1 } else { prev_color_idx = 2 } } else if last_color_idx == 1 { /* Current was green, previous must be blue or red */ if dp[i+1][1] - green_costs[i+1] == dp[i][0] { prev_color_idx = 0 } else { prev_color_idx = 2 } } else { /* Current was red, previous must be blue or green */ if dp[i+1][2] - red_costs[i+1] == dp[i][0] { prev_color_idx = 0 } else { prev_color_idx = 1 } } /* Set the color for day i and update last_color_idx for the next iteration */ result[i] = colors[prev_color_idx] last_color_idx = prev_color_idx } /* Return the final sequence */ return result } ``` ### Code Implementation **C++** ```cpp #include #include #include #include using namespace std; class solution { public: vector lowest_cost(const vector& blue_costs, const vector& green_costs, const vector& red_costs) { int n = blue_costs.size(); if (n == 0) { return {}; } vector> dp(n, vector(3)); dp[0][0] = blue_costs[0]; dp[0][1] = green_costs[0]; dp[0][2] = red_costs[0]; for (int i = 1; i < n; ++i) { dp[i][0] = blue_costs[i] + min(dp[i - 1][1], dp[i - 1][2]); dp[i][1] = green_costs[i] + min(dp[i - 1][0], dp[i - 1][2]); dp[i][2] = red_costs[i] + min(dp[i - 1][0], dp[i - 1][1]); } vector result(n); long long min_cost = min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}); int last_color_idx; if (min_cost == dp[n - 1][0]) last_color_idx = 0; else if (min_cost == dp[n - 1][1]) last_color_idx = 1; else last_color_idx = 2; char colors[] = {'b', 'g', 'r'}; result[n - 1] = colors[last_color_idx]; for (int i = n - 2; i >= 0; --i) { int prev_color_idx = -1; if (last_color_idx == 0) { // Current blue if (dp[i + 1][0] - blue_costs[i + 1] == dp[i][1]) prev_color_idx = 1; else prev_color_idx = 2; } else if (last_color_idx == 1) { // Current green if (dp[i + 1][1] - green_costs[i + 1] == dp[i][0]) prev_color_idx = 0; else prev_color_idx = 2; } else { // Current red if (dp[i + 1][2] - red_costs[i + 1] == dp[i][0]) prev_color_idx = 0; else prev_color_idx = 1; } result[i] = colors[prev_color_idx]; last_color_idx = prev_color_idx; } return result; } }; ``` **Python** ```python import sys class solution: def lowest_cost(self, blue_costs, green_costs, red_costs): n = len(blue_costs) if n == 0: return [] dp = [[0] * 3 for _ in range(n)] dp[0][0] = blue_costs[0] dp[0][1] = green_costs[0] dp[0][2] = red_costs[0] for i in range(1, n): dp[i][0] = blue_costs[i] + min(dp[i - 1][1], dp[i - 1][2]) dp[i][1] = green_costs[i] + min(dp[i - 1][0], dp[i - 1][2]) dp[i][2] = red_costs[i] + min(dp[i - 1][0], dp[i - 1][1]) result = [''] * n colors = ['b', 'g', 'r'] min_cost = min(dp[n - 1]) last_color_idx = dp[n - 1].index(min_cost) result[n - 1] = colors[last_color_idx] for i in range(n - 2, -1, -1): prev_color_idx = -1 if last_color_idx == 0: # Current blue if dp[i + 1][0] - blue_costs[i + 1] == dp[i][1]: prev_color_idx = 1 else: prev_color_idx = 2 elif last_color_idx == 1: # Current green if dp[i + 1][1] - green_costs[i + 1] == dp[i][0]: prev_color_idx = 0 else: prev_color_idx = 2 else: # Current red if dp[i + 1][2] - red_costs[i + 1] == dp[i][0]: prev_color_idx = 0 else: prev_color_idx = 1 result[i] = colors[prev_color_idx] last_color_idx = prev_color_idx return result ``` **Java** ```java import java.util.*; class Solution { public static char[] lowest_cost(int[] blue_costs, int[] green_costs, int[] red_costs) { int n = blue_costs.length; if (n == 0) { return new char[0]; } long[][] dp = new long[n][3]; dp[0][0] = blue_costs[0]; dp[0][1] = green_costs[0]; dp[0][2] = red_costs[0]; for (int i = 1; i < n; i++) { dp[i][0] = blue_costs[i] + Math.min(dp[i - 1][1], dp[i - 1][2]); dp[i][1] = green_costs[i] + Math.min(dp[i - 1][0], dp[i - 1][2]); dp[i][2] = red_costs[i] + Math.min(dp[i - 1][0], dp[i - 1][1]); } char[] result = new char[n]; char[] colors = {'b', 'g', 'r'}; long min_cost = Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])); int last_color_idx; if (min_cost == dp[n - 1][0]) last_color_idx = 0; else if (min_cost == dp[n - 1][1]) last_color_idx = 1; else last_color_idx = 2; result[n - 1] = colors[last_color_idx]; for (int i = n - 2; i >= 0; i--) { int prev_color_idx = -1; if (last_color_idx == 0) { // Current blue if (dp[i + 1][0] - blue_costs[i + 1] == dp[i][1]) prev_color_idx = 1; else prev_color_idx = 2; } else if (last_color_idx == 1) { // Current green if (dp[i + 1][1] - green_costs[i + 1] == dp[i][0]) prev_color_idx = 0; else prev_color_idx = 2; } else { // Current red if (dp[i + 1][2] - red_costs[i + 1] == dp[i][0]) prev_color_idx = 0; else prev_color_idx = 1; } result[i] = colors[prev_color_idx]; last_color_idx = prev_color_idx; } return result; } } ``` **JavaScript** ```javascript class Solution { static lowest_cost(blue_costs, green_costs, red_costs) { const n = blue_costs.length; if (n === 0) { return []; } const dp = Array(n).fill(0).map(() => Array(3).fill(0)); dp[0][0] = blue_costs[0]; dp[0][1] = green_costs[0]; dp[0][2] = red_costs[0]; for (let i = 1; i < n; i++) { dp[i][0] = blue_costs[i] + Math.min(dp[i - 1][1], dp[i - 1][2]); dp[i][1] = green_costs[i] + Math.min(dp[i - 1][0], dp[i - 1][2]); dp[i][2] = red_costs[i] + Math.min(dp[i - 1][0], dp[i - 1][1]); } const result = Array(n); const colors = ['b', 'g', 'r']; const min_cost = Math.min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]); let last_color_idx; if (min_cost === dp[n - 1][0]) last_color_idx = 0; else if (min_cost === dp[n - 1][1]) last_color_idx = 1; else last_color_idx = 2; result[n - 1] = colors[last_color_idx]; for (let i = n - 2; i >= 0; i--) { let prev_color_idx = -1; if (last_color_idx === 0) { // Current blue if (dp[i + 1][0] - blue_costs[i + 1] === dp[i][1]) prev_color_idx = 1; else prev_color_idx = 2; } else if (last_color_idx === 1) { // Current green if (dp[i + 1][1] - green_costs[i + 1] === dp[i][0]) prev_color_idx = 0; else prev_color_idx = 2; } else { // Current red if (dp[i + 1][2] - red_costs[i + 1] === dp[i][0]) prev_color_idx = 0; else prev_color_idx = 1; } result[i] = colors[prev_color_idx]; last_color_idx = prev_color_idx; } return result; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n)` — We iterate once to fill the DP table and once for path reconstruction. - **Space Complexity:** `O(n)` — The DP table of size `n x 3` uses linear space.