DEV Community

Dev Cookies
Dev Cookies

Posted on

📝 Blog 2: 1D DP Patterns – Linear Problems

Dynamic Programming shines in linear problems, where states depend on previous elements. These are the building blocks for harder multidimensional problems.

🔑 1. General Template for 1D DP

When solving a linear DP problem:

  1. Define state → What does dp[i] represent?
  2. Base case(s) → Where does computation start?
  3. Transition → How do we compute dp[i] using earlier states?
  4. Answer → Usually dp[n-1] or dp[n].

👉 Think of dp[i] as: the best/optimal/possible way up to index i.

📌 Category 1: Fibonacci-Type Problems

🔹 Problem: Climbing Stairs

You can take 1 or 2 steps at a time. How many ways to reach step n?

  • State: dp[i] = number of ways to reach step i
  • Base case: dp[0] = 1, dp[1] = 1
  • Transition: 
 dp[i] = dp[i-1] + dp[i-2]
Enter fullscreen mode Exit fullscreen mode

✅ Java Code

public class ClimbStairs { public static int climbStairs(int n) { if (n <= 2) return n; int[] dp = new int[n+1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } public static void main(String[] args) { System.out.println(climbStairs(5)); // 8 } }
Enter fullscreen mode Exit fullscreen mode

⚡ Optimization: Use 2 variables instead of full array.

📌 Category 2: Max Sum Problems

🔹 Problem: House Robber

You can’t rob adjacent houses. Max money?

  • State: dp[i] = max money till house i
  • Base cases: 
 dp[0] = nums[0] dp[1] = max(nums[0], nums[1])
Enter fullscreen mode Exit fullscreen mode
  • Transition: 
 dp[i] = max(dp[i-1], nums[i] + dp[i-2])
Enter fullscreen mode Exit fullscreen mode

✅ Java Code

public class HouseRobber { public static int rob(int[] nums) { if (nums.length == 1) return nums[0]; int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]); } return dp[nums.length-1]; } public static void main(String[] args) { int[] houses = {2,7,9,3,1}; System.out.println(rob(houses)); // 12 } }
Enter fullscreen mode Exit fullscreen mode

📌 Category 3: Reachability Problems

🔹 Problem: Jump Game

Given jumps at each index, can you reach last index?

  • State: dp[i] = true if last index reachable from i
  • Transition: For each i, check if any j reachable leads to true.

✅ Greedy better, but DP works.

✅ Java Code

public class JumpGame { public static boolean canJump(int[] nums) { boolean[] dp = new boolean[nums.length]; dp[0] = true; for (int i = 0; i < nums.length; i++) { if (!dp[i]) continue; for (int j = 1; j <= nums[i] && i+j < nums.length; j++) { dp[i+j] = true; } } return dp[nums.length-1]; } public static void main(String[] args) { int[] nums = {2,3,1,1,4}; System.out.println(canJump(nums)); // true } }
Enter fullscreen mode Exit fullscreen mode

📌 Category 4: Maximum Subarray (Kadane’s Algorithm)

🔹 Problem: Maximum Subarray Sum

Find contiguous subarray with max sum.

  • State: dp[i] = max sum of subarray ending at i
  • Transition: 
 dp[i] = max(nums[i], nums[i] + dp[i-1])
Enter fullscreen mode Exit fullscreen mode

✅ Java Code

public class Kadane { public static int maxSubArray(int[] nums) { int maxSum = nums[0]; int current = nums[0]; for (int i = 1; i < nums.length; i++) { current = Math.max(nums[i], current + nums[i]); maxSum = Math.max(maxSum, current); } return maxSum; } public static void main(String[] args) { int[] nums = {-2,1,-3,4,-1,2,1,-5,4}; System.out.println(maxSubArray(nums)); // 6 } }
Enter fullscreen mode Exit fullscreen mode

📌 Category 5: Minimum Cost Problems

🔹 Problem: Min Cost Climbing Stairs

You can take 1 or 2 steps, each with a cost. Find min cost to reach top.

  • State: dp[i] = min cost to reach step i
  • Transition: 
 dp[i] = cost[i] + min(dp[i-1], dp[i-2])
Enter fullscreen mode Exit fullscreen mode

✅ Java Code

public class MinCostClimb { public static int minCostClimbingStairs(int[] cost) { int n = cost.length; int[] dp = new int[n+1]; for (int i = 2; i <= n; i++) { dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]); } return dp[n]; } public static void main(String[] args) { int[] cost = {10, 15, 20}; System.out.println(minCostClimbingStairs(cost)); // 15 } }
Enter fullscreen mode Exit fullscreen mode

📌 Category 6: Partition Problems

🔹 Problem: Partition Equal Subset Sum

Can array be partitioned into two subsets with equal sum?

  • State: dp[i] = whether sum i is achievable
  • Base case: dp[0] = true
  • Transition: 
 dp[i] = dp[i] || dp[i-num]
Enter fullscreen mode Exit fullscreen mode

✅ Java Code

public class PartitionSubset { public static boolean canPartition(int[] nums) { int sum = 0; for (int num : nums) sum += num; if (sum % 2 != 0) return false; int target = sum / 2; boolean[] dp = new boolean[target+1]; dp[0] = true; for (int num : nums) { for (int i = target; i >= num; i--) { dp[i] = dp[i] || dp[i-num]; } } return dp[target]; } public static void main(String[] args) { int[] nums = {1,5,11,5}; System.out.println(canPartition(nums)); // true } }
Enter fullscreen mode Exit fullscreen mode

⚡ Optimization Techniques in 1D DP

  1. Space Optimization
  • Use 2 variables (O(1) space) for Fibonacci-like problems.
  • Use 1D rolling array for Knapsack.
  1. Prefix/Suffix Trick
  • Sometimes computing prefix/suffix max/min helps avoid nested loops.
  1. Greedy vs DP
  • Problems like Jump Game can be solved faster with greedy, but DP gives intuition.

❌ Common Pitfalls

  • Forgetting base case initialization.
  • Confusing “ways” vs “min/max value”.
  • Iterating in wrong order (important in subset/knapsack problems).
  • Using 2D dp when 1D is enough.

🎯 Key Takeaways

  • 1D DP = linear problems where dp[i] depends on a few previous states.
  • Categories: Fibonacci, Max Sum, Reachability, Min Cost, Partitioning.
  • Practice moving from simple → harder: Climb Stairs → House Robber → Kadane → Partition.
  • Optimize for space whenever possible.

Top comments (0)