Dynamic Programming

Posted on: February 1, 2025 Posted by: rahulgite Comments: 0

Problem 1: Climbing Stairs

Explanation:

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Approach:

  1. Dynamic Programming:
    • Use dp[i] = dp[i-1] + dp[i-2], as the number of ways to reach i is the sum of the ways to reach i-1 and i-2.
  2. Optimized Space Approach:
    • Instead of using an array, use two variables to track previous two steps.

Time & Space Complexity:

  • Time Complexity: O(n), since we compute for each step once.
  • Space Complexity: O(1), since we use only two variables.

Java Implementation:

public class ClimbingStairs {
    /**
     * Calculates the number of distinct ways to climb n stairs.
     * @param n - number of steps
     * @return number of ways to reach the top
     */
    public static int climbStairs(int n) {
        if (n <= 2) return n;
        int first = 1, second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
    
    public static void main(String[] args) {
        int n = 5;
        System.out.println("Output: " + climbStairs(n));
    }
}

Example:

Input:

n = 5

Output:

8

Edge Cases Considered:

  • n = 1 → Should return 1.
  • n = 2 → Should return 2.
  • Large n → Should efficiently compute values.

Problem 2: House Robber

Explanation:

Given an integer array nums representing the amount of money in houses, return the maximum amount you can rob without robbing adjacent houses.

Approach:

  1. Dynamic Programming:
    • Use dp[i] = max(dp[i-1], dp[i-2] + nums[i]), where dp[i] represents the maximum money up to house i.
  2. Optimized Space Approach:
    • Track only the last two computed values instead of using an array.

Time & Space Complexity:

  • Time Complexity: O(n), since we process each house once.
  • Space Complexity: O(1), using only two variables.

Java Implementation:

public class HouseRobber {
    /**
     * Computes the maximum amount that can be robbed without robbing adjacent houses.
     * @param nums - array of house values
     * @return maximum amount that can be robbed
     */
    public static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int prev1 = 0, prev2 = 0;
        for (int num : nums) {
            int temp = Math.max(prev1, prev2 + num);
            prev2 = prev1;
            prev1 = temp;
        }
        return prev1;
    }
    
    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println("Output: " + rob(nums));
    }
}

Example:

Input:

nums = [2,7,9,3,1]

Output:

12

Edge Cases Considered:

  • Empty array → Should return 0.
  • Single house → Should return its value.
  • Multiple houses with different values → Should select non-adjacent ones optimally.

Problem 3: Coin Change 2

Explanation:

Given coins of different denominations and a total amount, return the number of ways to make that amount.

Approach:

  1. Dynamic Programming:
    • Use dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]], where dp[i][j] is the number of ways to make amount j using the first i coins.
  2. Optimized Space Approach:
    • Use a 1D array dp[j], where dp[j] += dp[j - coin].

Time & Space Complexity:

  • Time Complexity: O(n * m), where n is the number of coins and m is the target amount.
  • Space Complexity: O(m), using a 1D array.

Java Implementation:

public class CoinChange2 {
    /**
     * Computes the number of ways to make amount using given coins.
     * @param amount - total amount
     * @param coins - array of coin denominations
     * @return number of ways to make the amount
     */
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }
    
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
        System.out.println("Output: " + change(amount, coins));
    }
}

Example:

Input:

amount = 5, coins = [1, 2, 5]

Output:

4

Edge Cases Considered:

  • No coins available → Should return 0.
  • Amount 0 → Should return 1.
  • Multiple ways to make the amount → Should compute all possible combinations.

Problem 4: Unique Paths

Explanation:

A robot is located at the top-left corner of an m x n grid. The robot can only move either down or right at any point in time. Find the number of unique paths to the bottom-right corner.

Approach:

  1. Dynamic Programming:
    • Use dp[i][j] = dp[i-1][j] + dp[i][j-1], where dp[i][j] represents the number of unique paths to (i, j).
  2. Optimized Space Approach:
    • Use a 1D array to store previous row computations.

Time & Space Complexity:

  • Time Complexity: O(m * n), since we traverse the grid once.
  • Space Complexity: O(n), using a 1D array.

Java Implementation:

public class UniquePaths {
    /**
     * Computes the number of unique paths in an m x n grid.
     * @param m - number of rows
     * @param n - number of columns
     * @return number of unique paths
     */
    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
    
    public static void main(String[] args) {
        int m = 3, n = 7;
        System.out.println("Output: " + uniquePaths(m, n));
    }
}

Example:

Input:

m = 3, n = 7

Output:

28

Edge Cases Considered:

  • Single row or column → Should return 1.
  • Small and large grids → Should compute efficiently.

Problem 5: Longest Increasing Subsequence

Explanation:

Given an array nums, return the length of the longest increasing subsequence.

Approach:

  1. Dynamic Programming:
    • Use dp[i] = max(dp[i], dp[j] + 1), iterating over previous values j < i.
  2. Binary Search Optimization:
    • Use a list to keep track of increasing elements and update using binary search.

Time & Space Complexity:

  • Time Complexity: O(n log n), using binary search.
  • Space Complexity: O(n), for tracking elements.

Java Implementation:

import java.util.*;

public class LongestIncreasingSubsequence {
    /**
     * Computes the length of the longest increasing subsequence.
     * @param nums - input array
     * @return length of longest subsequence
     */
    public static int lengthOfLIS(int[] nums) {
        List<Integer> lis = new ArrayList<>();
        for (int num : nums) {
            int pos = Collections.binarySearch(lis, num);
            if (pos < 0) pos = -(pos + 1);
            if (pos < lis.size()) lis.set(pos, num);
            else lis.add(num);
        }
        return lis.size();
    }
    
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Output: " + lengthOfLIS(nums));
    }
}

Example:

Input:

nums = [10,9,2,5,3,7,101,18]

Output:

4

Edge Cases Considered:

  • Single element array → Should return 1.
  • All elements equal → Should return 1.
  • Already sorted array → Should return n.

Problem 6: Edit Distance

Explanation:

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2 using insertions, deletions, and substitutions.

Approach:

  1. Dynamic Programming:
    • Use dp[i][j], where dp[i][j] represents the minimum edits to convert word1[0...i] to word2[0...j].
    • Recurrence: If characters match, dp[i][j] = dp[i-1][j-1], otherwise 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Time & Space Complexity:

  • Time Complexity: O(m * n), where m and n are string lengths.
  • Space Complexity: O(min(m, n)), using optimized space.

Java Implementation:

public class EditDistance {
    /**
     * Computes the minimum edit distance between two words.
     * @param word1 - first word
     * @param word2 - second word
     * @return minimum number of edits required
     */
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n + 1];
        
        for (int j = 0; j <= n; j++) dp[j] = j;
        
        for (int i = 1; i <= m; i++) {
            int prev = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev;
                } else {
                    dp[j] = 1 + Math.min(prev, Math.min(dp[j - 1], dp[j]));
                }
                prev = temp;
            }
        }
        return dp[n];
    }
    
    public static void main(String[] args) {
        String word1 = "horse", word2 = "ros";
        System.out.println("Output: " + minDistance(word1, word2));
    }
}

Example:

Input:

word1 = "horse", word2 = "ros"

Output:

3

Edge Cases Considered:

  • Identical words → Should return 0.
  • One word empty → Should return the length of the other word.
  • Similar words with minor differences → Should correctly compute edits.

Leave a Comment