2-D Dynamic Programming

There is an `m x n` grid where you are allowed to move either down or to the right at any point in time. Given the two integers `m` and `n`, return the number of possible unique paths that can be taken from the top-left corner of the grid (`grid[0][0]`) to the bottom-right corner (`grid[m - 1][n - 1]`). You may assume the output will fit in a **32-bit** integer. **Example 1:**  ```java Input: m = 3, n = 6 Output: 21 ``` **Example 2:** ```java Input: m = 3, n = 3 Output: 6 ``` **Constraints:** * `1 <= m, n <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the grid. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think in terms of recursion and visualize it as a decision tree, where we have two choices at each step. Can you determine the base condition and recurrence relation? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We recursively traverse the grid using row <code>i</code> and column <code>j</code>. At each step, we explore both possibilities: moving down or moving right, ensuring we do not go out of bounds. If we reach the bottom-right cell, we return <code>1</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> This approach has exponential complexity. Can you think of a way to optimize the recursion? Maybe you should consider using a dynamic programming approach. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results of recursive calls and avoid recalculations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>

Given two strings `text1` and `text2`, return the length of the *longest common subsequence* between the two strings if one exists, otherwise return `0`. A **subsequence** is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters. * For example, `"cat"` is a subsequence of `"crabt"`. A **common subsequence** of two strings is a subsequence that exists in both strings. **Example 1:** ```java Input: text1 = "cat", text2 = "crabt" Output: 3 ``` Explanation: The longest common subsequence is "cat" which has a length of 3. **Example 2:** ```java Input: text1 = "abcd", text2 = "abcd" Output: 4 ``` **Example 3:** ```java Input: text1 = "abcd", text2 = "efgh" Output: 0 ``` **Constraints:** * `1 <= text1.length, text2.length <= 1000` * `text1` and `text2` consist of only lowercase English characters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the length of the string <code>text1</code> and <code>n</code> is the length of the string <code>text2</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think in terms of recursion and visualize it as a decision tree. Can you determine the possible decisions at each step? Maybe you should consider iterating through both strings recursively at the same time. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> At each recursion step, we have two choices: if the characters at the current indices of both strings match, we move both indices forward and extend the subsequence. Otherwise, we explore two paths by advancing one index at a time and recursively finding the longest subsequence. We return the maximum length between these two choices. This approach is exponential. Can you think of a way to optimize it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We return <code>0</code> if either index goes out of bounds. To optimize, we can use memoization to cache recursive call results and avoid redundant calculations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>

You are given an integer array `prices` where `prices[i]` is the price of NeetCoin on the `ith` day. You may buy and sell one NeetCoin multiple times with the following restrictions: * After you sell your NeetCoin, you cannot buy another one on the next day (i.e., there is a cooldown period of one day). * You may only own at most one NeetCoin at a time. You may complete as many transactions as you like. Return the **maximum profit** you can achieve. **Example 1:** ```java Input: prices = [1,3,4,0,4] Output: 6 ``` Explanation: Buy on day 0 (price = 1) and sell on day 1 (price = 3), profit = 3-1 = 2. Then buy on day 3 (price = 0) and sell on day 4 (price = 4), profit = 4-0 = 4. Total profit is 2 + 4 = 6. **Example 2:** ```java Input: prices = [1] Output: 0 ``` **Constraints:** * `1 <= prices.length <= 5000` * `0 <= prices[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think in terms of recursion and visualize it as a decision tree. Can you determine the possible decisions at each recursion step? Also, can you identify the base cases and the essential information that needs to be tracked during recursion? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> At each recursion step, we can buy only if we haven't already bought a coin, or we can sell if we own one. When buying, we subtract the coin value, and when selling, we add it. We explore all possible buying and selling options recursively, iterating through the coins from left to right using index <code>i</code>. For the cooldown condition, if we buy a coin, we increment the index <code>i</code> by two. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use a boolean variable <code>canBuy</code> to indicate whether buying is allowed at the current recursive step. If we go out of bounds, we return <code>0</code>. This approach is exponential. Can you think of a way to optimize it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results of recursive calls and avoid recalculations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>

You are given an integer array `coins` representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer `amount` representing a target amount of money. Return the number of distinct combinations that total up to `amount`. If it's impossible to make up the amount, return `0`. You may assume that you have an unlimited number of each coin and that each value in `coins` is unique. **Example 1:** ```java Input: amount = 4, coins = [1,2,3] Output: 4 ``` Explanation: * 1+1+1+1 = 4 * 1+1+2 = 4 * 2+2 = 4 * 1+3 = 4 **Example 2:** ```java Input: amount = 7, coins = [2,4] Output: 0 ``` **Constraints:** * `1 <= coins.length <= 100` * `1 <= coins[i] <= 5000` * `0 <= amount <= 5000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n * a)</code> time and <code>O(n * a)</code> space, where <code>n</code> is the number of coins and <code>a</code> is the given amount. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> As we need to find the total number of combinations, think in terms of recursion and visualize it as a decision tree where multiple coin choices are available at each recursion step. Can you determine a way to allow picking the same coin multiple times? Maybe you should consider the decisions made at each recursion step. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> The given coins are unique. We recursively iterate through the coins array using index <code>i</code>, tracking the collected amount along the current path. At each step, we can either skip the current coin or pick it, ensuring the total does not exceed the target. To allow picking the same coin multiple times, we recurse with the same index but an updated amount, generating different combinations. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> If we reach the target amount, we return <code>1</code>. The recursion stops if the index goes out of bounds. We count all possible ways and return the total. This approach is exponential. Can you think of a way to optimize it? Maybe you should consider an approach to avoid redundant computations. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>

You are given an array of integers `nums` and an integer `target`. For each number in the array, you can choose to either add or subtract it to a total sum. * For example, if `nums = [1, 2]`, one possible sum would be `"+1-2=-1"`. If `nums=[1,1]`, there are **two different ways** to sum the input numbers to get a sum of `0`: `"+1-1"` and `"-1+1"`. Return the number of **different ways** that you can build the expression such that the total sum equals `target`. **Example 1:** ```java Input: nums = [2,2,2], target = 2 Output: 3 ``` Explanation: There are 3 different ways to sum the input numbers to get a sum of 2. `+2 +2 -2 = 2` `+2 -2 +2 = 2` `-2 +2 +2 = 2` **Constraints:** * `1 <= nums.length <= 20` * `0 <= nums[i] <= 1000` * `-1000 <= target <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n * m)</code> time and <code>O(n * m)</code> space, where <code>n</code> is the size of the input array and <code>m</code> is the sum of all the elements in the array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think in terms of recursion and visualize it as a decision tree, where we have two choices at each recursion step: assigning a positive or negative sign. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We recursively iterate through the array using index <code>i</code>, tracking the current sum along the recursive path. Each step branches into two paths, and we sum the number of ways to reach the target. If the index <code>i</code> goes out of bounds, we return <code>1</code> if the current sum equals the target; otherwise, we return <code>0</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> This approach is exponential. We can use memoization to cache recursive call results and avoid redundant calculations. A hash map or a <code>2D</code> array with modifications can be used for caching. If using a <code>2D</code> array, the dimensions can be <code>(n * (2m + 1))</code>, where <code>n</code> is the array size and <code>m</code> represents the sum of the array elements. </p> </details>

You are given three strings `s1`, `s2`, and `s3`. Return `true` if `s3` is formed by **interleaving** `s1` and `s2` together or `false` otherwise. **Interleaving** two strings `s` and `t` is done by dividing `s` and `t` into `n` and `m` substrings respectively, where the following conditions are met * `|n - m| <= 1`, i.e. the difference between the number of substrings of `s` and `t` is at most `1`. * `s = s1 + s2 + ... + sn` * `t = t1 + t2 + ... + tm` * **Interleaving** `s` and `t` is `s1 + t1 + s2 + t2 + ...` or `t1 + s1 + t2 + s2 + ...` You may assume that `s1`, `s2` and `s3` consist of lowercase English letters. **Example 1:**  ```java Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa" Output: true ``` Explanation: We can split `s1` into `["aa", "aa"]`, `s2` can remain as `"bbbb"` and `s3` is formed by interleaving `["aa", "aa"]` and `"bbbb"`. **Example 2:** ```java Input: s1 = "", s2 = "", s3 = "" Output: true ``` **Example 3:** ```java Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy" Output: false ``` Explanation: We can't split `s3` into `["ab", "xz", "cy"]` as the order of characters is not maintained. **Constraints:** * `0 <= s1.length, s2.length <= 100` * `0 <= s3.length <= 200` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the length of the string <code>s1</code> and <code>n</code> is the length of the string <code>s2</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> If the sum of the characters in <code>s1</code> and <code>s2</code> does not equal <code>s3</code>, we return <code>false</code>. Think in terms of recursion and visualize it as a decision tree, where we explore different combinations of portions from both strings. Can you determine the possible decisions at each recursion step? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We recursively iterate through the strings using indices <code>i</code>, <code>j</code>, and <code>k</code> for <code>s1</code>, <code>s2</code>, and <code>s3</code>, respectively. At each step, we extend the current path in two directions based on whether the <code>k</code>-th character of <code>s3</code> matches the current character of <code>s1</code> or <code>s2</code>. If any path returns <code>true</code>, we immediately return <code>true</code>. If <code>k</code> goes out of bounds, it means we have successfully formed the interleaved string, so we return <code>true</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> This approach is exponential. Can you think of a way to optimize it? Since <code>k</code> depends on <code>i</code> and <code>j</code>, it can be treated as a constant, as we can derive <code>k</code> using <code>i + j</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results of recursive calls and avoid redundant computations. Treating <code>i</code> and <code>j</code> as states, we can use a hash map or a <code>2D</code> array to store the results. </p> </details>

You are given a 2-D grid of integers `matrix`, where each integer is greater than or equal to `0`. Return the length of the longest strictly increasing path within `matrix`. From each cell within the path, you can move either horizontally or vertically. You **may not** move **diagonally**. **Example 1:**  ```java Input: matrix = [[5,5,3],[2,3,6],[1,1,1]] Output: 4 ``` Explanation: The longest increasing path is `[1, 2, 3, 6]` or `[1, 2, 3, 5]`. **Example 2:**  ```java Input: matrix = [[1,2,3],[2,1,4],[7,6,5]] Output: 7 ``` Explanation: The longest increasing path is `[1, 2, 3, 4, 5, 6, 7]`. **Constraints:** * `1 <= matrix.length, matrix[i].length <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the given matrix. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> If we move from one cell to an adjacent cell with a greater value, we won't revisit a cell, as the path is strictly increasing. A brute force approach would be to run a <code>dfs</code> from every cell and return the longest path found. This approach is exponential. Can you think of a way to optimize it to avoid redundant calculations? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>

You are given two strings `s` and `t`, both consisting of english letters. Return the number of distinct **subsequences** of `s` which are equal to `t`. **Example 1:** ```java Input: s = "caaat", t = "cat" Output: 3 ``` Explanation: There are 3 ways you can generate `"cat"` from `s`. * (c)aa(at) * (c)a(a)a(t) * (ca)aa(t) **Example 2:** ```java Input: s = "xxyxy", t = "xy" Output: 5 ``` Explanation: There are 5 ways you can generate `"xy"` from `s`. * (x)x(y)xy * (x)xyx(y) * x(x)(y)xy * x(x)yx(y) * xxy(x)(y) **Constraints:** * `1 <= s.length, t.length <= 1000` * `s` and `t` consist of English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the length of the string <code>s</code> and <code>n</code> is the length of the string <code>t</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think in terms of recursion and visualize it as a decision tree, as we need to explore all subsequences of <code>s</code>. Can you determine the possible decisions at each recursion step? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We recursively iterate through the strings using indices <code>i</code> and <code>j</code> for <code>s</code> and <code>t</code>, respectively. At each recursion step, we can either skip the current character of <code>s</code> or include it in the current path if it matches the current character of <code>t</code>. Can you determine the base conditions for this recursive function? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> If index <code>j</code> goes out of bounds, we return <code>1</code> as a valid subsequence is found. If index <code>i</code> goes out of bounds first, we return <code>0</code>. At each recursion step, we return the sum of both paths. This approach is exponential. Can you think of a way to optimize it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>

You are given two strings `word1` and `word2`, each consisting of lowercase English letters. You are allowed to perform three operations on `word1` an unlimited number of times: * Insert a character at any position * Delete a character at any position * Replace a character at any position Return the minimum number of operations to make `word1` equal `word2`. **Example 1:** ```java Input: word1 = "monkeys", word2 = "money" Output: 2 ``` Explanation: `monkeys` -> `monkey` (remove `s`) `monkey` -> `money` (remove `k`) **Example 2:** ```java Input: word1 = "neatcdee", word2 = "neetcode" Output: 3 ``` Explanation: `neatcdee` -> `neetcdee` (replace `a` with `e`) `neetcdee` -> `neetcde` (remove last `e`) `neetcde` -> `neetcode` (insert `o`) **Constraints:** * `0 <= word1.length, word2.length <= 100` * `word1` and `word2` consist of lowercase English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> and <code>n</code> are the lengths of the strings <code>word1</code> and <code>word2</code>, respectively. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think in terms of recursion and visualize it as a decision tree, as we have choices at each recursion step. Can you determine the recurrence relation and base cases? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We recursively iterate through the strings using indices <code>i</code> and <code>j</code> for <code>word1</code> and <code>word2</code>, respectively. If the characters at the current indices match, we increment both indices without counting an operation. Otherwise, we have three choices: insert the character at the current index of <code>word1</code> (increment <code>j</code>), delete the current character of <code>word1</code> (increment <code>i</code>), or replace the character at index <code>i</code> in <code>word1</code> (increment both <code>i</code> and <code>j</code>). </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> If index <code>i</code> goes out of bounds, we return the number of remaining characters in <code>word2</code> (using insert operations). If index <code>j</code> goes out of bounds, we return the number of remaining characters in <code>word1</code> (using delete operations). At each step, we return the minimum operation path. This approach is exponential. Can you think of a way to optimize it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results and avoid redundant calculations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>

You are given an array of integers `nums` of size `n`. The `ith` element represents a balloon with an integer value of `nums[i]`. You must burst all of the balloons. If you burst the `ith` balloon, you will receive `nums[i - 1] * nums[i] * nums[i + 1]` coins. If `i - 1` or `i + 1` goes out of bounds of the array, then assume the out of bounds value is 1. Return the maximum number of coins you can receive by bursting all of the balloons. **Example 1:** ```java Input: nums = [4,2,3,7] Output: 143 Explanation: nums = [4,2,3,7] --> [4,3,7] --> [4,7] --> [7] --> [] coins = 4*2*3 + 4*3*7 + 1*4*7 + 1*7*1 = 143 ``` **Constraints:** * `n == nums.length` * `1 <= n <= 300` * `0 <= nums[i] <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n ^ 3)</code> time and <code>O(n ^ 2)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to simulate the process recursively by passing the array to the recursive function. At each step, iterate through the array, pop an element, and recursively apply the same process to the two subarrays on both sides of the popped element, returning the maximum result from all recursive paths. This approach is exponential. Can you think of a way to optimize it? Maybe you should consider observing the subproblems instead of modifying the array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Instead of passing the array, we can pass the range of indices <code>l</code> and <code>r</code> that need to be processed. We pad the input array with <code>1</code>s on both sides for easier computation, but <code>l</code> and <code>r</code> represent the first and last indices of the original input array. Can you think of a reverse engineering approach for popping elements? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We determine the result by considering each element as the last one to be popped in the current range. For each element, we calculate its value by multiplying it with the elements at <code>l - 1</code> and <code>r + 1</code>, then recursively solve the subproblems for the ranges <code>(l, i - 1)</code> and <code>(i + 1, r)</code>, where <code>i</code> is the current element in the given range. Can you think of a way to optimize and avoid redundant calculations? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a <code>2D</code> array can be used to store results since the recursive function parameters <code>l</code> and <code>r</code> are within the range of the input array size. </p> </details>

You are given an input string `s` consisting of lowercase english letters, and a pattern `p` consisting of lowercase english letters, as well as `'.'`, and `'*'` characters. Return `true` if the pattern matches the **entire** input string, otherwise return `false`. * `'.'` Matches any single character * `'*'` Matches zero or more of the preceding element. **Example 1:** ```java Input: s = "aa", p = ".b" Output: false ``` Explanation: Regardless of which character we choose for the `'.'` in the pattern, we cannot match the second character in the input string. **Example 2:** ```java Input: s = "nnn", p = "n*" Output: true ``` Explanation: `'*'` means zero or more of the preceding element, `'n'`. We choose `'n'` to repeat three times. **Example 3:** ```java Input: s = "xyz", p = ".*z" Output: true ``` Explanation: The pattern `".*"` means zero or more of any character, so we choose `".."` to match `"xy"` and `"z"` to match `"z"`. **Constraints:** * `1 <= s.length <= 20` * `1 <= p.length <= 20` * Each appearance of `'*'`, will be preceded by a valid character or `'.'`. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(m * n)</code> time and <code>O(m * n)</code> space, where <code>m</code> is the length of the string <code>s</code> and <code>n</code> is the length of the string <code>p</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think in terms of recursion and visualize it as a decision tree, where we explore different combinations to match the strings when encountering <code>*</code>. Multiple decisions are made at each step to find a valid matching path. Can you determine the possible decisions at each recursion step? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We recursively iterate through the strings using indices <code>i</code> and <code>j</code> for <code>s</code> and <code>p</code>, respectively. If the characters match or <code>p[j]</code> is <code>'.'</code>, we increment both <code>i</code> and <code>j</code> to process the remaining strings. When the next character of string <code>p</code> is <code>'*'</code>, we have two choices: skip it (treating it as zero occurrences) or match one or more characters (if <code>s[i]</code> matches <code>p[j]</code>), incrementing <code>i</code> accordingly. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> If both indices go out of bounds, we return <code>true</code>; otherwise, we return <code>false</code>. If any recursive path returns <code>true</code>, we immediately return <code>true</code>. This approach is exponential. Can you think of a way to optimize it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a <code>2D</code> array can be used to store these results. </p> </details>