Dynamic Programming

Problem Requirements Given an integer array nums, find a nonempty contiguous subarray with the greatest product and return that product. Contiguous means the chosen elements must be adjacent: you cannot skip a number in between. Nonempty means you must choose at least one element. Return only the product, not the range or its length. Input: nums = [2, 3, -2, 4] Output: 6 Explanation: The contiguous subarray [2, 3] has the greatest product, 2 * 3 = 6. Input: nums = [-2, 0, -1] Output: 0 Explanation: You cannot skip 0 and treat -2 and -1 as a subarray. Choosing [0] gives 0. The constraints are 1 <= len(nums) <= 20000 and -10 <= nums[i] <= 10. The problem guarantees that the product of any subarray fits in a signed 32-bit integer. The input is never empty, but it may contain negatives and zeros. ...

Problem Requirements Given a positive integer n, return the minimum number of positive perfect squares whose sum is exactly n. A perfect square is the square of an integer, such as 1 = 1², 4 = 2², 9 = 3², or 16 = 4². The sum must equal n exactly. You may use the same perfect square any number of times. Return only the count, not the decomposition. The order of the terms does not affect the answer. Constraint: 1 <= n <= 10^4. Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4 uses 3 perfect squares. Input: n = 13 Output: 2 Explanation: 13 = 9 + 4 uses 2 perfect squares. This guide builds the solution in Python 3.9+. It assumes familiarity with functions, loops, and basic recursion, and develops the dynamic programming reasoning step by step. ...

Problem Input and Output Input: a string s and a list of strings wordDict Every element in wordDict is an available word, and the same word may be reused Output: return True if s can be split into one or more dictionary words; otherwise, return False The split must cover the entire string without skipping or reordering characters Examples Input: s = "leetcode", wordDict = ["leet", "code"] Output: True Explanation: "leetcode" can be split into "leet" + "code" Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: True Explanation: "apple" + "pen" + "apple"; the same word may be reused Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: False Explanation: some prefixes can be formed, but the split cannot cover the entire string Constraints 1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s and wordDict[i] contain only lowercase English letters All strings in wordDict are unique Step 1: Make the Completed Prefix Visible Start with one concrete question. For s = "leetcode", before deciding whether the whole string can be split, can we record how much of it has already been completed? ...

Problem Input and Output Input: an integer array nums, where nums[i] is the money in the i-th house. The houses form a circle. Adjacent houses cannot both be robbed, so houses 0 and n - 1 cannot both be robbed either. Output: the maximum amount of money that can be robbed without triggering the alarm. Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 1000. Examples Input: nums = [2,3,2] Output: 3 Explanation: Houses 0 and 2 are adjacent around the circle, so they cannot both be robbed; rob the house containing 3. Input: nums = [1,2,3,1] Output: 4 Explanation: We can rob indices 0 and 2, or indices 1 and 3. Input: nums = [1,2,3] Output: 3 This tutorial uses Python only and starts with the smallest first-last conflict. ...

Problem Requirements You are given an integer array coins, where coins[i] is a coin denomination, and a non-negative integer amount. The goal is to make a total exactly equal to amount. You may use each denomination any number of times. Return the minimum number of coins needed to make amount. If the amount cannot be made, return -1. If amount = 0, no coins are needed, so the answer is 0. The constraints are 1 <= coins.length <= 12, 1 <= coins[i] <= 2^31 - 1, and 0 <= amount <= 10^4. All coin denominations are distinct. ...

Problem Input and Output Input: an integer array nums Output: return the length of the longest strictly increasing subsequence in nums A subsequence preserves the relative order of the original array, but it does not need to be contiguous, so elements may be skipped If the selected indices are i_1 < i_2 < ... < i_k, they must also satisfy nums[i_1] < nums[i_2] < ... < nums[i_k] The subsequence is non-empty, so at least one element must be selected Constraints: 1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4 Examples Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: [2,5,7,101] is a strictly increasing subsequence of length 4; its elements do not need to be contiguous in the original array. Input: nums = [0,1,0,3,2,3] Output: 4 Explanation: [0,1,2,3] has length 4; [0,1,3] is also valid, but shorter. This article uses Python only. We start with the local question “how long can a subsequence ending at each position be?” and gradually turn it into a runnable solution. ...

Problem Requirements Given an array nums containing only positive integers, determine whether all its elements can be split into two subsets whose sums are equal. Input and Output Input: an integer array nums Output: return True if the array can be split equally; otherwise, return False Every element must belong to exactly one of the two subsets. No element may be discarded or used twice Examples Input: nums = [1,5,11,5] Output: True Explanation: [1,5,5] and [11] both have a sum of 11 Input: nums = [1,2,3,5] Output: False Explanation: the total is 11, and an odd total cannot be split equally Input: nums = [1,1] Output: True Explanation: put one 1 in each subset Constraints According to the LeetCode 416 statement: ...

Problem Requirement Given a non-negative integer n, return an array answer of length n + 1. For every index: answer[i] = the number of 1 bits in the binary representation of i The requested range includes both 0 and n. LeetCode provides this method contract: countBits(n: int) -> List[int] Example 1 Input: n = 2 Output: [0,1,1] 0 -> 0 -> 0 set bits 1 -> 1 -> 1 set bit 2 -> 10 -> 1 set bit Example 2 Input: n = 5 Output: [0,1,1,2,1,2] Constraints 0 <= n <= 10^5 Step 1: This Time We Need Every Answer From 0 to n LeetCode 191 asks for one integer’s set-bit count. For n = 5, this problem asks for all six related answers: ...

Problem Input and Output Input: an integer array nums nums[i] is the money in the i-th house Adjacent houses cannot both be robbed Output: return the maximum amount of money that can be robbed Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 400 Examples Input: nums = [1,2,3,1] Output: 4 Explanation: rob indices 0 and 2, for 1 + 3 = 4 Input: nums = [2,7,9,3,1] Output: 12 Explanation: rob indices 0, 2, and 4, for 2 + 9 + 1 = 12 This article uses Python only and derives 1D DP from the conflict between two choices. ...

Problem Input and Output Input: an integer n Meaning: climb to the top of the n-step staircase Each move can climb 1 or 2 steps Output: return the number of distinct ways to reach the top Constraints: 1 <= n <= 45 Examples Input: n = 2 Output: 2 Explanation: 1+1, 2 Input: n = 3 Output: 3 Explanation: 1+1+1, 1+2, 2+1 This article uses Python only and derives the final solution step by step from the meaning of dp[i]. ...