Master climbing stairs, decode ways, jump game, and other classic single-array DP patterns.
Published March 16, 2025
One-dimensional DP problems maintain a dp array where each element represents the answer for a subproblem involving a prefix or suffix of the input.
Climbing Stairs — how many ways to reach step n (1 or 2 steps at a time):
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
// dp[i] = dp[i-1] + dp[i-2] (same as Fibonacci)
}
Decode Ways — count valid decodings of a digit string:
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1; // empty string
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int oneDigit = s.charAt(i-1) - '0';
int twoDigits = Integer.parseInt(s.substring(i-2, i));
if (oneDigit != 0) dp[i] += dp[i-1];
if (twoDigits >= 10 && twoDigits <= 26) dp[i] += dp[i-2];
}
return dp[n];
}
Jump Game — can you reach the last index?
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // stuck
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
// Greedy, not strictly DP, but shows the 1D scan pattern
}
Jump Game II — minimum jumps to reach last index:
public int jump(int[] nums) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == curEnd) { jumps++; curEnd = farthest; } // must take a jump
}
return jumps;
}
Minimum Cost Climbing Stairs:
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int a = cost[0], b = cost[1];
for (int i = 2; i < n; i++) {
int c = cost[i] + Math.min(a, b);
a = b; b = c;
}
return Math.min(a, b);
}
Coin Change — minimum coins to reach amount:
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // infinity
dp[0] = 0;
for (int i = 1; i <= amount; i++)
for (int coin : coins)
if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
Maximum Product Subarray:
public int maxProduct(int[] nums) {
int max = nums[0], min = nums[0], result = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) { int tmp = max; max = min; min = tmp; } // negative flips
max = Math.max(nums[i], max * nums[i]);
min = Math.min(nums[i], min * nums[i]);
result = Math.max(result, max);
}
return result;
}
Word Break — can s be segmented using words in dictionary?
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++)
for (int j = 0; j < i; j++)
if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
return dp[s.length()];
}