Dynamic Programming

LeetCode 198: House Robber, Deriving 1D DP from Rob or Skip

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

LeetCode 70: Climbing Stairs, Deriving 1D DP from dp[i]

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

LeetCode 746: Min Cost Climbing Stairs, Deriving DP from the Top Position

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

Hot100: Maximum Subarray (Kadane O(n) ACERS Guide)

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