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

✅ 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
    }
}

⚡ 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])

• Transition:

  dp[i] = max(dp[i-1], nums[i] + dp[i-2])

✅ 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
    }
}

---

📌 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
    }
}

---

📌 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])

✅ 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
    }
}

---

📌 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])

✅ 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
    }
}

---

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

✅ 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
    }
}

---

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

---