Dynamic Programming

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]. ...

Problem Input and Output Input: an integer array cost cost[i] is the cost of stepping on stair i Each move can climb 1 or 2 steps You may start from index 0 or index 1 Output: return the minimum cost to reach the top Constraints: 2 <= cost.length <= 1000, 0 <= cost[i] <= 999 Examples Input: cost = [10,15,20] Output: 15 Explanation: start from index 1, pay 15, then reach the top directly Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Start from the Top Position of [10,15,20] Look at the small example: ...

Subtitle / Summary Maximum Subarray is the classic 1D DP / greedy template. This ACERS guide explains Kadane’s idea, engineering use cases, and runnable multi-language solutions. Reading time: 10–12 min Tags: Hot100, dynamic programming, greedy SEO keywords: Maximum Subarray, Kadane, dynamic programming, O(n), Hot100 Meta description: Kadane O(n) maximum subarray sum with engineering scenarios and multi-language code. A — Algorithm Problem Restatement Given an integer array nums, find the contiguous subarray with the largest sum (must contain at least one element) and return the sum. ...