1-D Dynamic Programming

You are given an integer `n` representing the number of steps to reach the top of a staircase. You can climb with either `1` or `2` steps at a time. Return the number of distinct ways to climb to the top of the staircase. **Example 1:** ```java Input: n = 2 Output: 2 ``` Explanation: 1. `1 + 1 = 2` 2. `2 = 2` **Example 2:** ```java Input: n = 3 Output: 3 ``` Explanation: 1. `1 + 1 + 1 = 3` 2. `1 + 2 = 3` 3. `2 + 1 = 3` **Constraints:** * `1 <= n <= 30` <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 number of steps. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> At each step, we have two choices: climb one step or climb two steps. We can solve this by considering both options and picking the minimum using recursion. However, this results in <code>O(2^n)</code> time complexity. Can you think of a better approach? Perhaps, try to avoid the repeated work of calling recursion more than once with same parameters. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> This is a Dynamic Programming problem. We can use Memoization to avoid repeated work. Create an <code>n</code>-sized array <code>cache</code> to store the results of recursive calls. When the recursion is called with specific parameters, return the stored value if it has already been computed. How would you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We start the initial recursion with <code>i = 0</code>, indicating that we are at position <code>i</code>. We first check if the current recursion with the given <code>i</code> is already cached. If it is, we immediately return the stored value. Otherwise, we perform the recursion, store the result in the cache, and then return it. Can you think of the base condition to stop the recursion? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> At each recursion, we perform two recursive calls: one for climbing one step and another for climbing two steps. The minimum return value between the two is the result for the current recursion. The base condition is to return <code>0</code> if <code>i == n</code>. This is a one-dimensional dynamic programming problem, which can be further optimized using more advanced techniques. </p> </details>

You are given an array of integers `cost` where `cost[i]` is the cost of taking a step from the `ith` floor of a staircase. After paying the cost, you can step to either the `(i + 1)th` floor or the `(i + 2)th` floor. You may choose to start at the index `0` or the index `1` floor. Return the minimum cost to reach the top of the staircase, i.e. just past the last index in `cost`. **Example 1:** ```java Input: cost = [1,2,3] Output: 2 ``` Explanation: We can start at index = `1` and pay the cost of `cost[1] = 2` and take two steps to reach the top. The total cost is `2`. **Example 2:** ```java Input: cost = [1,2,1,2,1,1,1] Output: 4 ``` Explanation: Start at index = `0`. * Pay the cost of `cost[0] = 1` and take two steps to reach index = `2`. * Pay the cost of `cost[2] = 1` and take two steps to reach index = `4`. * Pay the cost of `cost[4] = 1` and take two steps to reach index = `6`. * Pay the cost of `cost[6] = 1` and take one step to reach the top. * The total cost is `4`. **Constraints:** * `2 <= cost.length <= 100` * `0 <= cost[i] <= 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(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of steps on the staircase. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Can you find the recurrence relation to solve the problem, given that at each step we have two options: going one step or two steps? Consider drawing a decision tree where we branch into two paths at each step. By exploring every path, we can get the minimum cost. However, this results in an <code>O(2^n)</code> time solution. Can you think of a better approach? Is there any repeated work in the decision tree that we can optimize? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> The recurrence relation can be expressed as <code>cost[i] + min(dfs(i + 1), dfs(i + 2))</code>, where <code>i</code> is the current position and <code>dfs</code> is the recursive function. To avoid recalculating the result of a recursive call multiple times, we can use Memoization. Initialize a <code>cache</code> array of size <code>n</code>, where <code>n</code> is the number of steps on the staircase. How would you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We start the recursion from positions <code>0</code> and <code>1</code>. At each recursive step, before computing the result, we check if the result for the current position has already been calculated. If it has, we return the stored value. Otherwise, we calculate the result for the current position, store it in the cache, and then return the result. What can be the base condition for this recursion to stop? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> The base condition would be to return <code>0</code> if we are at the top of the staircase <code>i >= n</code>. This is a one-dimensional dynamic programming problem. We can further optimize the memoization solution by using advanced techniques such as Bottom-Up dynamic programming based on the recurrance relation. </p> </details>

You are given an integer array `nums` where `nums[i]` represents the amount of money the `i`th house has. The houses are arranged in a straight line, i.e. the `i`th house is the neighbor of the `(i-1)`th and `(i+1)`th house. You are planning to rob money from the houses, but you cannot rob **two adjacent houses** because the security system will automatically alert the police if two adjacent houses were *both* broken into. Return the *maximum* amount of money you can rob **without** alerting the police. **Example 1:** ```java Input: nums = [1,1,3,3] Output: 4 ``` Explanation: `nums[0] + nums[2] = 1 + 3 = 4`. **Example 2:** ```java Input: nums = [2,9,8,3,6] Output: 16 ``` Explanation: `nums[0] + nums[2] + nums[4] = 2 + 8 + 6 = 16`. **Constraints:** * `1 <= nums.length <= 100` * `0 <= nums[i] <= 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(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of houses. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Can you think of this problem in terms of recursion? Consider drawing a decision tree where, at each step, we can choose to rob the house or skip it. If we rob the current house, we cannot rob the next or the previous house. Can you derive a recurrence relation to solve the problem? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can recursively start from the first house and branch paths accordingly. If we rob the current house, we skip the next house; otherwise, we move to the next house. The recurrence relation can be expressed as <code>max(nums[i] + dfs(i + 2), dfs(i + 1))</code>, where <code>i</code> is the current house and <code>dfs</code> is the recursive function. Can you determine the base condition to stop the recursion? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> The base condition would be to return <code>0</code> when <code>i</code> goes out of bounds. This recursion can leads to <code>O(2^n)</code> time solution. Can you think of a better way? Maybe you should try to avoid recalculating the result for a recursive call. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use Memoization to avoid recalculating the result multiple times for a recursive call. By storing the result of each recursive call in a hash map or an array using <code>i</code> as the parameter, we can immediately return the stored result if the recursion is called with the same <code>i</code> value again. Further optimization can be achieved using advanced techniques like Bottom-Up dynamic programming. </p> </details>

You are given an integer array `nums` where `nums[i]` represents the amount of money the `i`th house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors. You are planning to rob money from the houses, but you cannot rob **two adjacent houses** because the security system will automatically alert the police if two adjacent houses were *both* broken into. Return the *maximum* amount of money you can rob **without** alerting the police. **Example 1:** ```java Input: nums = [3,4,3] Output: 4 ``` Explanation: You cannot rob `nums[0] + nums[2] = 6` because `nums[0]` and `nums[2]` are adjacent houses. The maximum you can rob is `nums[1] = 4`. **Example 2:** ```java Input: nums = [2,9,8,3,6] Output: 15 ``` Explanation: You cannot rob `nums[0] + nums[2] + nums[4] = 16` because `nums[0]` and `nums[4]` are adjacent houses. The maximum you can rob is `nums[1] + nums[4] = 15`. **Constraints:** * `1 <= nums.length <= 100` * `0 <= nums[i] <= 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(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the number of houses. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> First, consider solving the problem to get the maximum money after robbing without the condition that 'the first and last houses are adjacent'. Can you express this using a recurrence relation? Perhaps you could draw a decision tree, as at each step, you can either rob the current house and skip the next one or skip the current house and move to the next. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> The recurrence relation can be expressed as <code>max(nums[i] + dfs(i + 2), dfs(i + 1))</code>, where <code>i</code> is the current house and <code>dfs</code> is the recursive function. The base condition for this recursion would be to return <code>0</code> when <code>i</code> goes out of bounds. This solution results in <code>O(2^n)</code> time complexity because, at each recursive step, we branch into two paths. Can you think of a way to avoid recalculating the result for the same recursive call multiple times? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use memoization to store the result of a recursive function in a hash map or an array and immediately return this value when the function is called again with the same parameter values. How would you implement this? How would you solve the problem if the first and last houses are adjacent to each other? Perhaps you should consider skipping any one house between the two. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can create two arrays from the given array. The first will include houses from the first house to the second-to-last house, and the second will include houses from the second house to the last house. We can run the recursive function on both arrays independently and return the maximum result between the two. Advanced techniques such as bottom-up dynamic programming can further optimize the solution. </p> </details>

Given a string `s`, return the longest substring of `s` that is a *palindrome*. A **palindrome** is a string that reads the same forward and backward. If there are multiple palindromic substrings that have the same length, return any one of them. **Example 1:** ```java Input: s = "ababd" Output: "bab" ``` Explanation: Both "aba" and "bab" are valid answers. **Example 2:** ```java Input: s = "abbc" Output: "bb" ``` **Constraints:** * `1 <= s.length <= 1000` * `s` contains only digits and 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(n^2)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the given string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute-force solution would be to check if every substring is a palindrome and return the maximum length among all the palindromic substring lengths. This would be an <code>O(n^3)</code> time solution. Can you think of a better way? Perhaps you should consider thinking in terms of the center of a palindrome. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Iterate over the string with index <code>i</code> and treat the current character as the center. For this character, try to extend outward to the left and right simultaneously, but only if both characters are equal. Update the result variable accordingly. How would you implement this? Can you consider both cases: even-length and odd-length palindromes? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Maintain two variables, <code>resLen</code> and <code>res</code>, which denote the length of the longest palindrome and the start index of that palindrome, respectively. At each index, you can create an odd-length palindrome starting at that index extending outward from both its left and right indices, i.e., <code>i - 1</code> and <code>i + 1</code>. How can you find the even-length palindrome for this index? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> For an even-length palindrome, consider expanding from indices <code>i</code> and <code>i + 1</code>. This two-pointer approach, extending from the center of the palindrome, will help find all palindromic substrings in the given string. Update the two result variables and return the substring starting at <code>res</code> with a length of <code>resLen</code>. </p> </details>

Given a string `s`, return the number of substrings within `s` that are palindromes. A **palindrome** is a string that reads the same forward and backward. **Example 1:** ```java Input: s = "abc" Output: 3 ``` Explanation: "a", "b", "c". **Example 2:** ```java Input: s = "aaa" Output: 6 ``` Explanation: "a", "a", "a", "aa", "aa", "aaa". Note that different substrings are counted as different palindromes even if the string contents are the same. **Constraints:** * `1 <= s.length <= 1000` * `s` consists 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(n^2)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the given string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute-force solution would be to check if every substring is a palindrome and return the total number of palindromic substrings. This would be an <code>O(n^3)</code> time solution. Can you think of a better way? Perhaps you should consider thinking in terms of the center of a palindrome. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Iterate over the string with index <code>i</code> and treat the current character as the center. For this character, try to extend outward to the left and right simultaneously, but only if both characters are equal. At each iteration, we increment the count of palindromes. How would you implement this? Can you consider both cases: even-length and odd-length palindromes? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Initialize a variable <code>res</code> to track the count of palindromes. At each index, create an odd-length palindrome starting at that index extending outward from both its left and right indices, i.e., <code>i - 1</code> and <code>i + 1</code>. How can you find the even-length palindrome for this index? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> For an even-length palindrome, consider expanding from indices <code>i</code> and <code>i + 1</code>. This two-pointer approach, extending from the center of the palindrome, will help find all palindromic substrings in the given string and return its count. </p> </details>

A string consisting of uppercase english characters can be encoded to a number using the following mapping: ```java 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" ``` To **decode** a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, `"1012"` can be mapped into: * `"JAB"` with the grouping `(10 1 2)` * `"JL"` with the grouping `(10 12)` The grouping `(1 01 2)` is invalid because `01` cannot be mapped into a letter since it contains a leading zero. Given a string `s` containing only digits, return the number of ways to **decode** it. You can assume that the answer fits in a **32-bit** integer. **Example 1:** ```java Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12). ``` **Example 2:** ```java Input: s = "01" Output: 0 ``` Explanation: "01" cannot be decoded because "01" cannot be mapped into a letter. **Constraints:** * `1 <= s.length <= 100` * `s` consists of digits <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 length of the given string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> The characters <code>A</code> through <code>Z</code> are mapped to the numbers from <code>1</code> to <code>26</code>. A mapped number can have at most <code>2</code> digits. In the given string of digits, we can explore all possible decodings by combining one or two consecutive digits. Think of this in terms of a decision tree and explore all paths. Can you derive a recurrence relation for this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Iterate over the string with index <code>i</code>. At each index, we have two choices: decode the current digit as a character with its mapped value, or combine the current digit with the next digit to form a two-digit value. The recurrence relation can be expressed as <code>dfs(i + 1) + dfs(i + 2)</code> where <code>dfs</code> is the recursive function. Also, consider edge cases, as not every two-digit number or a number with a leading zero is valid. How would you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> A brute-force recursive solution would result in <code>O(2^n)</code> time complexity. Can you think of a better way? Perhaps you should consider the repeated work of calling the recursion multiple times with the same parameter values and find a way to avoid this. Also, can you think about the base condition of this recursive function? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> The base condition is to return <code>1</code> if <code>i</code> goes out of bounds. If the current digit is <code>'0'</code>, return <code>0</code>, as no character maps to <code>'0'</code>, making the string invalid. Use memoization to avoid repeated work by caching recursion results in an array or hash map and returning the stored value when the result is already calculated. </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 fewest number of coins that you need to make up the *exact* target amount. If it is impossible to make up the amount, return `-1`. You may assume that you have an unlimited number of each coin. **Example 1:** ```java Input: coins = [1,5,10], amount = 12 Output: 3 ``` Explanation: 12 = 10 + 1 + 1. Note that we do not have to use every kind coin available. **Example 2:** ```java Input: coins = [2], amount = 3 Output: -1 ``` Explanation: The amount of 3 cannot be made up with coins of 2. **Example 3:** ```java Input: coins = [1], amount = 0 Output: 0 ``` Explanation: Choosing 0 coins is a valid way to make up 0. **Constraints:** * `1 <= coins.length <= 10` * `1 <= coins[i] <= 2^31 - 1` * `0 <= amount <= 10000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n * t)</code> time and <code>O(t)</code> space, where <code>n</code> is the number of coins and <code>t</code> is the given amount. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Think of this problem in terms of recursion and try to visualize the decision tree, as there are multiple choices at each step. We start with the given amount. At each step of recursion, we have <code>n</code> coins and branch into paths using coins that are less than or equal to the current amount. Can you express this in terms of a recurrence relation? Also, try to determine the base condition to stop the recursion. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> If the amount is <code>0</code>, we return <code>0</code> coins. The recurrence relation can be expressed as <code>min(1 + dfs(amount - coins[i]))</code>, where we return the minimum coins among all paths. This results in an <code>O(n ^ t)</code> solution, where <code>n</code> is the number of coins and <code>t</code> is the total amount. Can you think of a better approach? Perhaps consider the repeated work and find a way to avoid it. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use memoization to avoid the repeated work of calculating the result for each recursive call. A hash map or an array of size <code>t</code> can be used to cache the computed values for a specific <code>amount</code>. At each recursion step, we iterate over every coin and extend only the valid paths. If a result has already been computed, we return it from the cache instead of recalculating it. </p> </details>

Given an integer array `nums`, find a **subarray** that has the largest product within the array and return it. A **subarray** is a contiguous non-empty sequence of elements within an array. You can assume the output will fit into a **32-bit** integer. **Example 1:** ```java Input: nums = [1,2,-3,4] Output: 4 ``` **Example 2:** ```java Input: nums = [-2,-1] Output: 2 ``` **Constraints:** * `1 <= nums.length <= 1000` * `-10 <= nums[i] <= 10` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</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> A brute force solution would be to find the product for every subarray and then return the maximum among all the products. This would be an <code>O(n ^ 2)</code> approach. Can you think of a better way? Maybe you should think of a dynamic programming approach. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Try to identify a pattern by finding the maximum product for an array with two elements and determining what values are needed when increasing the array size to three. Perhaps you only need two values when introducing a new element. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We maintain both the minimum and maximum product values and update them when introducing a new element by considering three cases: starting a new subarray, multiplying with the previous max product, or multiplying with the previous min product. The max product is updated to the maximum of these three, while the min product is updated to the minimum. We also track a global max product for the result. This approach is known as Kadane's algorithm. </p> </details>

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of dictionary words. You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique. **Example 1:** ```java Input: s = "neetcode", wordDict = ["neet","code"] Output: true ``` Explanation: Return true because "neetcode" can be split into "neet" and "code". **Example 2:** ```java Input: s = "applepenapple", wordDict = ["apple","pen","ape"] Output: true ``` Explanation: Return true because "applepenapple" can be split into "apple", "pen" and "apple". Notice that we can reuse words and also not use all the words. **Example 3:** ```java Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"] Output: false ``` **Constraints:** * `1 <= s.length <= 200` * `1 <= wordDict.length <= 100` * `1 <= wordDict[i].length <= 20` * `s` and `wordDict[i]` consist of only 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(n * m * t)</code> time and <code>O(n)</code> space, where <code>n</code> is the length of the string <code>s</code>, <code>m</code> is the number of words in <code>wordDict</code>, and <code>t</code> is the maximum length of any word in <code>wordDict</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Try to think of this problem in terms of recursion, where we explore all possibilities. We iterate through the given string <code>s</code>, attempting to pick a word from <code>wordDict</code> that matches a portion of <code>s</code>, and then recursively continue processing the remaining string. Can you determine the recurrence relation and base condition? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> The base condition is to return <code>true</code> if we reach the end of the string <code>s</code>. At each recursive call with index <code>i</code> iterating through <code>s</code>, we check all words in <code>wordDict</code> and recursively process the remaining string by incrementing <code>i</code> by the length of the matched word. If any recursive path returns <code>true</code>, we immediately return <code>true</code>. However, this solution is exponential. Can you think of an optimization? Maybe you should consider an approach that avoids repeated work. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can avoid recalculating results for recursive calls by using memoization. Since we iterate with index <code>i</code>, we can use a hash map or an array of the same length as <code>s</code> to cache the results of recursive calls and prevent redundant computations. </p> </details>

Given an integer array `nums`, return the *length* of the longest strictly *increasing* subsequence. 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"`. **Example 1:** ```java Input: nums = [9,1,4,2,3,3,7] Output: 4 ``` Explanation: The longest increasing subsequence is [1,2,3,7], which has a length of 4. **Example 2:** ```java Input: nums = [0,3,1,3,2,3] Output: 4 ``` **Constraints:** * `1 <= nums.length <= 1000` * `-1000 <= nums[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 ^ 2)</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> A subsequence is formed by selecting elements while maintaining their order. Using recursion, we can generate all subsequences. The recursive function returns the length of the longest increasing subsequence up to index <code>i</code>, processing from left to right. At each step, we decide whether to include or exclude the current element. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Since the sequence must be increasing, we represent choices by adding <code>1</code> when including an element and <code>0</code> when excluding it. In recursion, how can we ensure the current element is greater than the previous one? Perhaps additional information is needed to process it. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can store the index of the previously chosen element as <code>j</code>, making it easier to process the current element at index <code>i</code>. If and only if <code>j == -1</code> or <code>nums[i] > nums[j]</code>, we include the current element and extend the recursive path. Can you determine the recurrence relation? At most, two recursive calls are made at each recursion step. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We stop the recursion when index <code>i</code> goes out of bounds and return <code>0</code> since no more elements can be added. The initial recursion call starts with <code>j = -1</code>. At each step, we include the current element if it is greater than the previous one and continue the recursion, or we exclude it and explore the next possibility. We return the maximum value obtained from both paths. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 5</summary> <p> The time complexity of this approach is exponential. We can use memoization to store results of recursive calls and avoid recalculations. A hash map or a <code>2D</code> array can be used to cache these results. </p> </details>

You are given an array of positive integers `nums`. Return `true` if you can partition the array into two subsets, `subset1` and `subset2` where `sum(subset1) == sum(subset2)`. Otherwise, return `false`. **Example 1:** ```java Input: nums = [1,2,3,4] Output: true ``` Explanation: The array can be partitioned as `[1, 4]` and `[2, 3]`. **Example 2:** ```java Input: nums = [1,2,3,4,5] Output: false ``` **Constraints:** * `1 <= nums.length <= 100` * `1 <= nums[i] <= 50` <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 * t)</code> time and <code>O(n * t)</code> space, where <code>n</code> is the size of the input array and <code>t</code> is half the sum of the array elements. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> If the sum of the array elements is not even, we can immediately return <code>false</code>. Think in terms of recursion, where we try to build a subset with a sum equal to half of the total sum. If we find such a subset, the remaining elements will automatically form another subset with the same sum. The entire array can also be considered as one subset, with the other being empty. Can you visualize this as a decision tree to process the array recursively? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We recursively iterate through the array with index <code>i</code>. At each step, we decide whether to include the current element in the subset or not. Instead of forming the subset explicitly, can you think of a better approach? Maybe you only need to track the subset sum rather than generating the subset itself. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can track the subset sum using a variable <code>curSum</code>. At each step, we make two recursive calls. If adding the current element does not exceed the target, we include it. If either path leads to a solution, we immediately return <code>true</code>. Can you determine the base case for this recursion? All elements in the array are positive. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> If <code>curSum</code> equals half the sum of the array elements, we return <code>true</code>. If index <code>i</code> goes out of bounds, we return <code>false</code>. This solution is exponential, but we can use memoization to cache recursive call results and avoid redundant computations. We can use a hash map or a <code>2D</code> array with dimensions <code>n * t</code>, where <code>n</code> is the size of the input array and <code>t</code> is half the sum of the input array elements. </p> </details>