Skip to content

DP LIS Advanced

Table of Contents

1626. Best Team With No Conflicts

673. Number of Longest Increasing Subsequence

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, binary indexed tree, segment tree

673. Number of Longest Increasing Subsequence - Python Solution
from typing import List


# DP - LIS
def findNumberOfLIS(nums: List[int]) -> int:
    if not nums:
        return 0

    n = len(nums)
    dp = [1 for _ in range(n)]
    counts = [1 for _ in range(n)]

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    counts[i] = counts[j]
                elif dp[j] + 1 == dp[i]:
                    counts[i] += counts[j]

    longest = max(dp)
    return sum(c for i, c in enumerate(counts) if dp[i] == longest)


nums = [1, 3, 5, 4, 7]
print(findNumberOfLIS(nums))  # 2

354. Russian Doll Envelopes

354. Russian Doll Envelopes - Python Solution
from typing import List


# DP - LIS
def maxEnvelopes(envelopes: List[List[int]]) -> int:
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    dp = []

    for w, h in envelopes:
        left, right = 0, len(dp)
        while left < right:
            mid = left + (right - left) // 2
            if dp[mid][1] < h:
                left = mid + 1
            else:
                right = mid
        if right == len(dp):
            dp.append((w, h))
        else:
            dp[right] = (w, h)

    return len(dp)


envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]
print(maxEnvelopes(envelopes))  # 3

1691. Maximum Height by Stacking Cuboids

960. Delete Columns to Make Sorted III

960. Delete Columns to Make Sorted III - Python Solution
from typing import List


# DP - LIS
def minDeletionSize(strs: List[str]) -> int:
    if not strs:
        return 0

    n = len(strs[0])
    dp = [1 for _ in range(n)]

    for i in range(n):
        for j in range(i):
            if all(row[j] <= row[i] for row in strs):
                dp[i] = max(dp[i], dp[j] + 1)

    return n - max(dp)

2407. Longest Increasing Subsequence II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, divide and conquer, dynamic programming, binary indexed tree, segment tree, queue, monotonic queue

1187. Make Array Strictly Increasing

1713. Minimum Operations to Make a Subsequence

3288. Length of the Longest Increasing Path

368. Largest Divisible Subset

Comments