DenCT/test-storage / DSA Notes /1D Dynamic Programming.md
DenCT's picture
|
download
raw
23.4 kB
metadata
tags:
  - notes
  - dynamic-programming
  - 1d-dynamic-programming
patterns: null

Climbing Stairs EASY

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?

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

[!info] Time and Space Complexity You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of steps.

Solution

  • Brute Force
    1. Brute force solution is to solve for all possible steps starting from 0, jump 1 or 2 steps.
    2. Base case is reaching the step outside the range n . When we reach a step beyond or on n , return 1 if we are at n or 0 if we are beyond n . If we are beyond n returning 0 indicates that we have reached outside the destination and that that step is invalid.
class Solution:
    def climbStairs(self, n: int) -> int:
        def helper(i):
            if i >= n:
                return int(i == n)
            return helper(i + 1) + helper(i + 2)
        return helper(0)

TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$

  • Memoization
    1. Same as brute force, but adding a cache to store the repeating cases
    2. Add a cache dictionary to store the distinct ways for each step, and use it when the case is revisited.
    class Solution:
        def climbStairs(self, n: int) -> int:
            cache = {}
            
            def helper(i):
                if i >= n:
                    return int(i == n)
                if i in cache:
                    return cache[i]
                
                cache[i] = helper(i + 1) + helper(i + 2)
                return cache[i]
            
            return helper(0)
    

TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$

Min Cost Climbing Stairs EASY

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

[!info] Time and Space Complexity You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of steps on the staircase.

Solution

  • Brute Force
    1. Using a recursion approach, we can visit all possible steps to check for best minimum cost.
    2. We start from 0 and move bottom to reach the final destination. Base case would be when we reach beyond the stairs. In that case, 0 will be returned, indicating that path is not possible.
    3. For all other cases, current + 1 and current + 2 steps will be visited and only the minimum of those two will be considered. With that the cost for current step will be added.
    4. When the recursion has finished for 0, for 1 the same will be done and the minimum of both will be returned.
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        size = len(cost)
        def helper(i):
            if i >= size:
                return 0
            return min(helper(i + 1), helper(i + 2)) + cost[i]
        return min(helper(0), helper(1))

TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$

  • Memoization
    1. Same as above, using recursion to cover all possible steps, but caching the visited steps for reference.
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        cache = {}
        n = len(cost)

        def helper(i):
            if i >= n:
                return 0
            if i in cache:
                return cache[i]
            cache[i] = min(helper(i + 1), helper(i + 2)) + cost[i]
            return cache[i]
        
        return min(helper(0), helper(1))

TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$

  • Optimised It's an iterative process of starting either from the end or from the beginning and comparing the cost of previous two steps. The answer would be the minimum of latest two prices.
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        size = len(cost)
        dp = [0] * (size + 1)
        dp[-1], dp[-2] = 0, cost[-1]
        for i in range(size - 2, -1, -1):
            dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]
        
        return min(dp[0], dp[1])

OR

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        size = len(cost)
        dp = [0] * (size + 1)
        dp[-1], dp[-2] = 0, cost[-1]
        for i in range(size - 2, -1, -1):
            dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]
        
        return min(dp[0], dp[1])

Minimum Path Sum MEDIUM

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Solution

First, we need to create a 2D cache grid to hold the traversal results, and fill it with -1. We start from the bottom right of the grid. Traverse the up and left cell of the bottom right cell, recursively and store the minimum of them in the cache cell in that row and column index. The loop breaking conditions are:

  • If the top-left cell is reached, return its value.
  • If we reach beyond the grid, return a huge number, indicating we reached beyond the grid. Lastly, if the cell was already visited, return its value from cache.
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        dp = [[-1 for _ in range(COL)] for _ in range(ROW)]
        return self.helper(ROW - 1, COL - 1, dp, grid)
    
    def helper(self, i, j, _dp, grid):
        if i == 0 and j == 0:
            return grid[0][0]
        if i < 0 or j < 0:
            return 9999999
        if _dp[i][j] != -1:
            return _dp[i][j]
        up = grid[i][j] + self.helper(i - 1, j, _dp, grid)
        left = grid[i][j] + self.helper(i, j - 1, _dp, grid)
        _dp[i][j] = min(up, left)
        return _dp[i][j]

Similarly, it can be solved in top-down approach too.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        dp = [[-1 for _ in range(COL)] for _ in range(ROW)]
        def helper(i, j):
            if i == ROW - 1 and j == COL - 1:
                return grid[i][j]
            if i >= ROW or j >= COL:
                return int(1e9)
            if dp[i][j] != -1:
                return dp[i][j]
            down = grid[i][j] + helper(i + 1, j)
            right = grid[i][j] + helper(i, j + 1)
            dp[i][j] = min(down, right)
            return dp[i][j]
        return helper(0, 0)

Coin Change

You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money. Return the fewest number of coins that you need to make up the exact target amount. If it is impossible to make up the amount, return -1. You may assume that you have an unlimited number of each coin. Example 1:

Input: coins = [1,5,10], amount = 12
Output: 3

Explanation: 12 = 10 + 1 + 1. Note that we do not have to use every kind coin available. Example 2:

Input: coins = [2], amount = 3
Output: -1

Explanation: The amount of 3 cannot be made up with coins of 2. Example 3:

Input: coins = [1], amount = 0
Output: 0

Explanation: Choosing 0 coins is a valid way to make up 0

Solution

The easiest approach is bottom up DP. We need to have an array of length amount + 1 to store the no of coins required to sum up to amount a, where a $\in$ [1, amount]. Loop over all possible a - c combinations and fill/update the values in the array. For a particular combination of a - c the no of coins required to get a sum of a - c is 1 + dp[a - c]. We compare this with existing value of dp[a- c] and chose minimum of the two.

[!info] Time and Space Complexity You should aim for a solution with O(n * t) time and O(t) space, where n is the number of coins and t is the given amount.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        tabu = [amount + 1] * (amount + 1)
        tabu[0] = 0

        for a in range(1, amount + 1):
            for c in coins:
                if a - c >= 0:
                    tabu[a] = min(tabu[a], 1 + tabu[a - c])
        print(tabu)
        return tabu[amount] if tabu[amount] != amount + 1 else -1

Edit Distance

You are given two strings word1 and word2, each consisting of lowercase English letters. You are allowed to perform three operations on word1 an unlimited number of times:

  • Insert a character at any position
  • Delete a character at any position
  • Replace a character at any position Return the minimum number of operations to make word1 equal word2. Example 1:
Input: word1 = "monkeys", word2 = "money"
Output: 2

Explanation:
monkeys -> monkey (remove s)
monkey -> monkey (remove k) Example 2:

Input: word1 = "neatcdee", word2 = "neetcode"
Output: 3

Explanation:
neatcdee -> neetcdee (replace a with e)
neetcdee -> neetcde (remove last e)
neetcde -> neetcode (insert o)

Solution

![[edit-distance-sol.png]] We create a 2D grid to store the minimum changes required to get the word2 string. The size of the grid will be (len(word1) + 1) * (len(word2) + 1). The last row and column of the grid will be the size of the sub-string from that column and row index, indicating that if the one string is empty, it would take "length of the other string" operations to get that string. We do a bottom-up traversal to get the minimum steps required to get the result string. There are two conditions to decide whether to insert, update or delete.

  • If the character at the positions are same, it is to be skipped.
  • else, the minimum of the 3 operations, insert, delete and update is to be considered and an additional cost is to be added.
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[
            float("inf") for _ in range(len(word2) + 1)
            ] for _ in range(len(word1) + 1)
        ]

        for i in range(len(word1) + 1):
            dp[i][-1] = len(word1) - i
        for i in range(len(word2) + 1):
            dp[-1][i] = len(word2) - i

        for i in range(len(word1) - 1, -1, -1):
            for j in range(len(word2) - 1, -1, -1):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i + 1][j + 1]
                else:
                    dp[i][j] = min(
                        dp[i + 1][j],
                        dp[i][j + 1],
                        dp[i + 1][j + 1]
                    ) + 1
        return dp[0][0]

Decode Ways MEDIUM

A string consisting of uppercase english characters can be encoded to a number using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, "1012" can be mapped into:

  • "JAB" with the grouping (10 1 2)
  • "JL" with the grouping (10 12) The grouping (1 01 2) is invalid because 01 cannot be mapped into a letter since it contains a leading zero. Given a string s containing only digits, return the number of ways to decode it. You can assume that the answer fits in a 32-bit integer. Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "01"
Output: 0

Explanation: "01" cannot be decoded because "01" cannot be mapped into a letter.

Solution

Think of decoding as breaking the string into valid 1- or 2-digit groups, each mapping to a letter. Use recursion with memoization: At each step, try decoding 1 digit (if valid) and 2 digits (if between "10"-"26"). Sum up the ways, caching results for efficiency.

class Solution:
    def numDecodings(self, s: str) -> int:
        cache = {len(s):1}
        
        def helper(i):
            if i in cache:
                return cache[i]
            if s[i] == "0":
                return 0

            res = helper(i + 1)
            if i + 1 < len(s) and (s[i] == "1" or (s[i] == "2" and s[i + 1] in "0123456")):
                res += helper(i + 2)
            cache[i] = res
            return cache[i]
        return helper(0)

Maximum Product Subarray MEDIUM

Given an integer array nums, find a subarray that has the largest product within the array and return it. A subarray is a contiguous non-empty sequence of elements within an array. You can assume the output will fit into a 32-bit integer. Example 1:

Input: nums = [1,2,-3,4]
Output: 4

Example 2:

Input: nums = [-2,-1]
Output: 2

Solution

We are using Kadane's algorithm here, which is kind of DP and Greedy Algorithm. Loop over each element in the list and calculate the maximum and minimum possible product till that position. Keep a result variable to store the result by modifying it whenever the max product increases.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = nums[0]
        curr_min, curr_max = 1, 1
        for i, num in enumerate(nums):
            temp = curr_max * num
            curr_max = max(num * curr_max, num * curr_min, num)
            curr_min = min(temp, num * curr_min, num)
            res = max(res, curr_max)
        return res

Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words. You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique. Example 1:

Input: s = "neetcode", wordDict = ["neet","code"]
Output: true

Explanation: Return true because "neetcode" can be split into "neet" and "code". Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen","ape"]
Output: true

Explanation: Return true because "applepenapple" can be split into "apple", "pen" and "apple". Notice that we can reuse words and also not use all the words. Example 3:

Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]
Output: false

Solution

Think of the problem as checking if you can build the string s by repeatedly "cutting off" dictionary words from its start. Use dynamic programming:

  • Create a boolean array dp, where dp[i] means "s[i:] can be segmented."
  • Start from the end of s; at each position, try every word in wordDict.
  • If a word matches the sub-string at s[i:] and the remaining part can be segmented (dp[i + len(word)]), mark dp[i] as True.
  • Use early exit to optimize.
    This approach efficiently checks all segmentations and avoids recomputation.
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
                if len(s) >= (i + len(w)) and s[i: i + len(w)] == w:
                    dp[i] = dp[i + len(w)]
                if dp[i]:
                    break
        return dp[0]

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

  • For example, "cat" is a subsequence of "crabt". Example 1:
Input: nums = [9,1,4,2,3,3,7]
Output: 4

Explanation: The longest increasing subsequence is [1,2,3,7], which has a length of 4. Example 2:

Input: nums = [0,3,1,3,2,3]
Output: 4

Solution

Treat the array as a sequence where for each position i, you want to know the length of the longest increasing sub-sequence starting at i. Use dynamic programming:

  • For each index, look forward to all higher-index elements larger than nums[i] and update dp[i] accordingly.
  • The answer is the maximum in dp. This captures all possible sub-sequences efficiently by building solutions for smaller sub-arrays first.
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        dp[len(nums) - 1] = 1
        for i in range(len(nums) - 1, -1, -1):
            for j in range(i + 1, len(nums)):
                if nums[i] < nums[j]:
                    dp[i] = max(dp[i], 1 + dp[j])
        return max(dp)

House Robber Leetcode MEDIUM

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Solution

  • Brute Force
    1. Start from the 0th house, move to i+2 th house or i+3 th house, chose the max amongst them and add the cost for i th house.
    2. Base case would be when we have reached the end of list or have reached beyond the list.
    class Solution:
        def rob(self, nums: List[int]) -> int:
            n = len(nums)
            def helper(i):
                if i >= n:
                    return 0
                return max(helper(i + 2), helper(i + 3)) + nums[i]
            return max(helper(0), helper(1))
    
  • Optimized (Memoization)
    1. Add a cache dictionary to store visited cases and use them when they are visited again.
    class Solution:
        def rob(self, nums: List[int]) -> int:
            n = len(nums)
            cache = {}
            def helper(i):
                if i >= n:
                    return 0
                if i in cache:
                    return cache[i]
                cache[i] = max(helper(i + 2), helper(i + 3)) + nums[i]
                return cache[i]
            return max(helper(0), helper(1))
    

House Robber II (Leetcode) MEDIUM

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbours. You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into. Return the maximum amount of money you can rob without alerting the police.

Input: nums = [3,4,3]
Output: 4

Input: nums = [2,9,8,3,6]
Output: 15

# Explanation: You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15.

[!info] Time and Space Complexity You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of houses.

Solution

  • Optimized (Memoization) The circular house constraint means if you rob house 0, you can't rob house n-1, so break this into two linear sub-problems: rob houses 0 to n-2 OR rob houses 1 to n-1. Use a flag parameter to track if house 0 was robbed - when flag = True, you cannot rob the last house. The recursion explores rob/skip decisions at each house while respecting this circular constraint, and the final answer is max(helper(0, True), helper(1, False)) to try both scenarios.
class Solution:
    def rob(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 1:
            return nums[size - 1]
        cache = {}
        def helper(i: int, flag: bool):
            if i >= size or (flag and i == size - 1):
                return 0
            if (i, flag) in cache:
                return cache[(i, flag)]
            cache[(i, flag)] = max(
                helper(i + 1, flag), 
                helper(i + 2, flag or i == 0) + nums[i],
              )
            return cache[(i, flag)]
        return max(helper(0, True), helper(1, False))

Longest Palindromic Sub-string MEDIUM

Given a string s, return the longest sub-string of s that is a palindrome. A palindrome is a string that reads the same forward and backward. If there are multiple palindromic sub-strings that have the same length, return any one of them. Example 1:

Input: s = "ababd"
Output: "bab"

Explanation: Both "aba" and "bab" are valid answers. Example 2:

Input: s = "abbc"
Output: "bb"

Solution

A non-DP solution will be to start from index 0 and spread out, checking all possible palindromes in the string. Then choosing the longest palindrome of them.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        self.max_string = s[0]
        self.max_len = 1
        def check_palindrome(i, j):
            while i >= 0 and j < len(s) and s[i] == s[j]:
                if len(s[i:j + 1]) > self.max_len:
                    self.max_len = j - i + 1
                    self.max_string = s[i:j + 1]
                i -= 1
                j += 1
        for i in range(len(s)):
            l, r = i, i
            check_palindrome(l, r)
            l, r = i, i + 1
            check_palindrome(l, r)
        return self.max_string

Xet Storage Details

Size:
23.4 kB
·
Xet hash:
5f5c33ed5c8f806932be15680dccd55abcd6789b169828bc52a585292fa7d592

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.