DP

Though Process

Step to build solution
- Decide what we have to do each step to bring us to the next valid state. Write down the recursive calls that implement this behavior
  - This can be think of at each step and each valid state, what are the choices that we can make
- Come up with a way to construct the next optimal solution with all the data you got from subsequent recursive calls. Add a base case and complete the recursive function. => Bruteforce solution
- Notice you have limited set of possible arguments combinations and cache the return value, so you avoid calling the function twice with the same argument => Memoization
- Convert Memoization solution to use Tabulation (Bottom-up approach)
Steps to convert a Top-down approach to Bottom-up approach
- Create a dp table having the size to fit all the cached values of dp function call
- Replace dp function definition by a loop over all possibles values of argument
  - Sometimes we need to be careful with the looping order. Since it is bottom up so we may need to iterate backward.
- Replace dp function calls by calls to the dp table we have created before
- Replace return call by setting dp cache value
- Remove a base case as it is not needed anymore, and make sure you've initialized the dp table with values that cover the base case

NOTES:

Sometimes it is easier to think about a bottom up approach rather than recursion.
Sometimes if we given a grid or maybe the state involve 2 variable we can use a MxN table for tabulation (2D Dynamic Programming)

Patterns

Path to reach a target

Practice: https://leetcode.com/list?selectedList=o9tcds8v
Statement:
Given a target find minimum (maximum) cost/path/sum to reach the target
Approach:
Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

Distinct Ways

Practice: https://leetcode.com/list?selectedList=o9tc73it
Statement:
Given a target find a number of distinct ways to reach the target
Approach
Sum all possible ways to reach the current state

routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]

Merging Interval

Practice: DP(merging intervals)
Statement:
Given a set of numbers find an optimal solution for a problem considering the current number and the best you can get from the left and right side
Approach
Find all optimal solutions for every interval and return the best possible answer. Get the best from the left and right sides and add a solution for the current position.

// from i to j
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]

DP on String

Practice: DP on strings
Statement
General problem statement for this pattern can vary but most of the time you are given two strings where lengths of those strings are not big
Given two string s1 and s2 return some result
Approach:
Most of the problems on this pattern requires a solution that can be accepted O(n^2) complexity. - DP on strings is usually, if not always, done by comparing two chars at a time.
[[13. DP#Longest Increasing Subsequence| Longest Increasing Subsequence Variant]]

// i - indexing string s1
// j - indexing string s2
for (int i = 1; i <= n; ++i) {
   for (int j = 1; j <= m; ++j) {
       if (s1[i-1] == s2[j-1]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}

If you are given one string s the approach may vary

for (int l = 1; l < n; ++l) {
   for (int i = 0; i < n-l; ++i) {
       int j = i + l;
       if (s[i] == s[j]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}

Decision Making

Practice: DP (decision making)
Statement
The general problem statement for this is for given situation decide whether to use or not to use the current state. So the problem requires you to make a decision at a current state.
Approach
If you decide to choose the current value use the previous result where the value was ignored; vice-versa, if your decide to ignore the current value use the previous result where value was used

2D DP

Use 2D DP if the problems depends on two incides or dimensions
- Knapsack problems where the states depends on the item index and the remaining capacity
- String problems: Where we compare characters of two string
- Grid problems: Path finding
This explain the thought process behind 2d array pretty well: https://www.youtube.com/watch?v=Mjy4hd2xgrs
- Ref: [[Blind 75-150#^df7a0c | Coin Change 2]]
Though process:
- Define the subproblem => what does dp[i][j] represents
- Identify the dimensions
- Initialize base case
- Define recurrence relation using subproblems
- How to iterate the tables
https://leetcode.com/problems/longest-common-subsequence/

# At each cell, store the result of the subproblem which is the LCS of the first character in text1 and first character in text2
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0 for i in range(n+1)] for j in range(m+1)]

        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i+1][j+1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])

        return dp[0][0]

https://leetcode.com/problems/edit-distance

# At each cell, store the minimum number of operations to convert the first i character of word1 to first j characters of word2
def minDistance(self, word1: str, word2: str) -> int:
        rows, cols = len(word1), len(word2)
        dp = [[0 for i in range(cols + 1)] for j in range(rows + 1)]

        for i in range(rows + 1):
            dp[i][0] = i
        for j in range(cols+1):
            dp[0][j] = j

        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    insert = dp[i][j-1] + 1
                    delete = dp[i-1][j] + 1
                    replace = dp[i-1][j-1] + 1
                    dp[i][j] = min(insert, delete, replace)

        return dp[-1][-1]

https://leetcode.com/problems/delete-operation-for-two-strings/

def minDistance(self, word1: str, word2: str) -> int:
        rows, cols = len(word1), len(word2)
        dp = [[0 for i in range(cols+1)] for j in range(rows + 1)]

        for i in range(rows + 1):
            dp[i][0] = i
        for j in range(cols + 1):
            dp[0][j] = j

        for i in range(1, rows+1):
            for j in range(1, cols+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    del1 = dp[i-1][j] + 1
                    del2 = dp[i][j-1] + 1
                    dp[i][j] = min(del1, del2)

        return dp[-1][-1]

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings

def minimumDeleteSum(self, s1: str, s2: str) -> int:
        rows, cols = len(s1) + 1, len(s2) + 1
        dp = [[0 for i in range(cols)] for j in range(rows)]

        for i in range(1, rows):
            dp[i][0] = dp[i-1][0] + ord(s1[i-1])

        for i in range(1, cols):
            dp[0][i] = dp[0][i-1] + ord(s2[i-1])

        for i in range(1, rows):
            for j in range(1, cols):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    del1 = dp[i-1][j] + ord(s1[i-1])
                    del2 = dp[i][j-1] + ord(s2[j-1])
                    dp[i][j] = min(del1, del2)

        return dp[-1][-1]

Variant

Longest Increasing Subsequence

Problems https://leetcode.com/problems/longest-increasing-subsequence/

# Travel from right to left so that we have case like 1,5,3 already handled as when we process a number, we know that all the number after it has already been processed
def lengthOfLIS(self, nums: List[int]) -> int:
        longest_ahead = [1] * len(nums)

        # candidate to find longest increasing subseqeunce is nums[i]
        for i in range(len(nums) -1, -1, -1):
            for j in range(i+1, len(nums)):
                if nums[i] < nums[j]:
                    longest_ahead[i] = max(longest_ahead[i], 1 + longest_ahead[j])

        return max(longest_ahead)

https://leetcode.com/problems/largest-divisible-subset/
https://leetcode.com/problems/russian-doll-envelopes/
https://leetcode.com/problems/maximum-length-of-pair-chain/
https://leetcode.com/problems/number-of-longest-increasing-subsequence/
https://leetcode.com/problems/delete-and-earn/

https://leetcode.com/problems/longest-string-chain/

Travel from right to left so that we have small case/subproblem already handled as when we process a number, we know that all the number after it has already been processed
- E.g: When we at 3, and we meet 5 we can already know what is the maximum that can be obtained after 5 (because we traverse from right to left and populate the memoization table )
The smallest subproblem is the element at the end of the array, at which there is always only 1 result. We traverse from right to left to use this smallest case and gradually build bigger case
If we need to know the number of times each subsequence length appear, we can have another array to save it, or instead of using a table like normal dp we can use a hashmap with key is the index and value is the length and its number of occurence
Ref [[Blind 75-150#^850c48 | Longest Increasing Subsequence]]

Algorithm

Kadane

Kadane’s algorithm is a popular method used to solve the maximum subarray sum problem efficiently. The goal is to find the maximum sum of a contiguous subarray within a given one-dimensional array of numbers, which can include negative values.

Algorithm

Iterate through the array: At each position, determine the maximum sum of the subarray ending at that position.
Dynamic programming principle:

Keep track of the maximum subarray sum ending at the current index (current_sum).
At each step, we update the current max as if we absolutely have to include the current value
- By doing this, the next iteration can build up on this and also update its local maximum
- This only works because we are dealing with contiguous subarray so to update one local maxima we need to know the local maximum right before it
Update current_sum as the maximum of:
- The current element itself (starting a new subarray).
- The sum of current_sum and the current element (extending the existing subarray).
Maintain a global max_sum to store the maximum sum encountered so far. ^a4fdb4

Base case: Start with the first element, as the maximum sum for a subarray including only the first element is itself.

Example A popular problem that utilizes this directly is https://leetcode.com/problems/maximum-subarray

 def maxSubArray(self, nums: List[int]) -> int:
    res = float('-inf')
    current = 0

    for num in nums:
        current = max(num, current + num)
        res = max(res, current)

    return res

https://leetcode.com/problems/maximum-product-subarray/

# DP 2 choices take current num or not take current num
def maxProduct(self, nums: List[int]) -> int:
        res = float("-inf")

        @lru_cache(None)
        def dp(index, product):
            nonlocal res
            if index >= len(nums):
                return product
            res = max(res, product*nums[index])
            take = dp(index+1, product*nums[index])
            not_take = dp(index+1, 1)

            return max(take, not_take)

        dp(0,1)
        return res

# Iterative
def maxProduct(self, nums: List[int]) -> int:
    res = float('-inf')
    curMax = 1
    curMin = 1

    for num in nums:
        tempCurMax = curMax
        curMax = max([num, curMax * num, curMin * num])
        curMin = min([num, curMin * num, tempCurMax * num])
        res = max([res, curMax, curMin])

    return res

While this algorithm may feels like a specific answer to a Leetcode question, it demonstrate an instance of Dynamic Programming principle where use the solution to subproblems to build solution for the overall problem.

Why Kadane’s Works

Local Optimality: At each step, we make the best local choice (add to the current subarray or start a new one).
Global Optimality: By tracking the global maximum (max_sum), we ensure that the solution considers all possibilities across the array.
Avoid Redundant Work: Instead of recalculating subarray sums repeatedly, Kadane’s reuses the computation from the previous step, achieving O(n) efficiency.

Mental Model [[13. DP#^a4fdb4]]

Kadane’s algorithm can be thought of as walking through the array while carrying a “bag” of the current subarray sum:
If adding an item to the bag makes the total heavier in a good way, keep it.
If the item is so heavy that it ruins the value of the bag, dump the bag and start fresh.
By the end of the walk, the heaviest bag you carried at any point is your answer.

When to Use Kadane's Algorithm 1. Contiguous Subarrays are Required
The problem must specifically ask for finding patterns in consecutive elements. For example:

Finding the subarray with the largest sum where all elements must be next to each other
Identifying a continuous sequence of stock prices that gives the maximum profit

https://leetcode.com/problems/maximum-subarray

 def maxSubArray(self, nums: List[int]) -> int:
    res = float('-inf')
    current = 0

    for num in nums:
        current = max(num, current + num)
        res = max(res, current)

    return res

https://leetcode.com/problems/maximum-sum-circular-subarray

https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion

2. Linear Time Complexity Needed

The problem involves large datasets where efficiency is crucial
You need a solution that scales linearly - O(n) time complexity
Brute force approaches (trying every possible subarray) would be too slow

https://leetcode.com/problems/best-time-to-buy-and-sell-stock

https://leetcode.com/problems/maximum-product-subarray/

# DP 2 choices take current num or not take current num
def maxProduct(self, nums: List[int]) -> int:
        res = float("-inf")

        @lru_cache(None)
        def dp(index, product):
            nonlocal res
            if index >= len(nums):
                return product
            res = max(res, product*nums[index])
            take = dp(index+1, product*nums[index])
            not_take = dp(index+1, 1)

            return max(take, not_take)

        dp(0,1)
        return res

# Iterative
def maxProduct(self, nums: List[int]) -> int:
    res = float('-inf')
    curMax = 1
    curMin = 1

    for num in nums:
        tempCurMax = curMax
        curMax = max([num, curMax * num, curMin * num])
        curMin = min([num, curMin * num, tempCurMax * num])
        res = max([res, curMax, curMin])

    return res

https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray

3. Simple Aggregation Required
The problem should involve straightforward calculations that can be done step by step:

Finding maximum or minimum sums
Calculating running products
Computing cumulative metrics that can be updated incrementally

https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted

https://leetcode.com/problems/substring-with-largest-variance

https://leetcode.com/problems/k-concatenation-maximum-sum

4. Mixed Positive and Negative Values
Kadane's algorithm excels when your data contains both positive and negative numbers because it can:

Intelligently decide whether to extend the current sequence or start fresh
Handle alternating patterns of gains and losses
Identify optimal subsequences even when surrounded by unfavorable values

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product

https://leetcode.com/problems/longest-turbulent-subarray

https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays

5. Common Variants and Applications
The core logic of Kadane's algorithm can be adapted for:

Maximum product subarray problems (with modifications for handling zero and negative values)
Circular array problems where the sequence can wrap around
Problems involving maximizing or minimizing sequences under similar constraints
Stock trading problems where you need to find the best buying and selling periods

https://leetcode.com/problems/minimum-size-subarray-sum

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k

When Not to Use Kadane's Algorithm 1. Non-Contiguous Subarrays

Kadane's algorithm only works when elements must be consecutive
If elements can be non-adjacent (like "maximum sum of non-adjacent elements"), you'll need different approaches like dynamic programming
Problems involving subsequences rather than subarrays need different solutions 2. Additional Constraints Present
When there are size restrictions (like "find maximum sum subarray of exactly length k")
If specific elements must be included or excluded
When there are multiple conditions beyond just finding a maximum sum 3. Complex Data Structures
Doesn't work directly with multi-dimensional arrays (like 2D matrices)
Not suitable for non-linear structures like graphs or trees
Requires significant modifications for anything beyond simple 1D arrays 4. Important Edge Cases
Arrays containing all negative numbers need special handling
Empty arrays require careful consideration
You must clarify if empty subarrays (length 0) are allowed in the solution 5. Subsequence Problems
Not suitable for problems like "longest increasing subsequence"
Can't handle problems where elements don't need to be consecutive
Won't work for problems involving picking arbitrary elements 6. Complex Objectives
When the goal involves multiple variables or constraints
Problems requiring array partitioning or complex optimization
When simple aggregation (sum/product) isn't the main objective

Alternative Approaches to Consider
When Kadane's isn't suitable, consider:

Dynamic Programming: For non-contiguous elements or additional constraints
Sliding Window: For fixed-length subarray problems
Divide and Conquer: When parallelization might help
Greedy Algorithms: For subsequence-based problems
Specialized Algorithms: For multi-dimensional or complex data structures

Key Questions to Ask
Before choosing Kadane's, check if:

Elements must be contiguous
The problem involves simple aggregation
There are additional constraints or requirements
The data structure is a simple 1D array
Edge cases are properly defined

DP

Though Process

Patterns

Path to reach a target

Similar Problem

Distinct Ways

Similar Problem

Merging Interval

Similar Problem

DP on String

Similar Problem

Decision Making

Similar Problem

2D DP

Variant

Longest Increasing Subsequence

Algorithm

Kadane

Resources

Though Process​

Patterns​

Path to reach a target​

Similar Problem​

Distinct Ways​

Similar Problem​

Merging Interval​

Similar Problem​

DP on String​

Similar Problem​

Decision Making​

Similar Problem​

2D DP​

Variant​

Longest Increasing Subsequence​

Algorithm​

Kadane​

Resources​

Though Process

Patterns

Path to reach a target

Similar Problem

Distinct Ways

Similar Problem

Merging Interval

Similar Problem

DP on String

Similar Problem

Decision Making

Similar Problem

2D DP

Variant

Longest Increasing Subsequence

Algorithm

Kadane

Resources