Skip to content

DP Multi-Dimensional

Table of Contents

2400. Number of Ways to Reach a Position After Exactly k Steps

1824. Minimum Sideway Jumps

3332. Maximum Points Tourist Can Earn

2370. Longest Ideal Subsequence

3176. Find the Maximum Length of a Good Subsequence I

3176. Find the Maximum Length of a Good Subsequence I - Python Solution
from collections import defaultdict
from typing import List


# DP
def maximumLength(nums: List[int], k: int) -> int:
    frequency = defaultdict(lambda: [0 for _ in range(k + 1)])
    dp = [0 for _ in range(k + 1)]

    for num in nums:
        f = frequency[num]
        for j in range(k, -1, -1):
            f[j] += 1
            if j > 0:
                f[j] = max(f[j], dp[j - 1] + 1)
            dp[j] = max(f[j], dp[j])

    return dp[-1]


nums = [1, 2, 1, 1, 3]
k = 2
print(maximumLength(nums, k))  # 4

1269. Number of Ways to Stay in the Same Place After Some Steps

3250. Find the Count of Monotonic Pairs I

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, dynamic programming, combinatorics, prefix sum

3218. Minimum Cost for Cutting Cake I

3122. Minimum Number of Operations to Satisfy Conditions

576. Out of Boundary Paths

403. Frog Jump

1223. Dice Roll Simulation

1320. Minimum Distance to Type a Word Using Two Fingers

3366. Minimum Array Sum

1575. Count All Possible Routes

3154. Find Number of Ways to Reach the K-th Stair

  • LeetCode | LeetCode CH (Hard)

  • Tags: math, dynamic programming, bit manipulation, memoization, combinatorics

2318. Number of Distinct Roll Sequences

1444. Number of Ways of Cutting a Pizza

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, dynamic programming, memoization, matrix, prefix sum

3320. Count The Number of Winning Sequences

3429. Paint House IV

1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

3193. Count the Number of Inversions

629. K Inverse Pairs Array

1079. Letter Tile Possibilities

1866. Number of Ways to Rearrange Sticks With K Sticks Visible

2312. Selling Pieces of Wood

3177. Find the Maximum Length of a Good Subsequence II

3177. Find the Maximum Length of a Good Subsequence II - Python Solution
from collections import defaultdict
from typing import List


# DP
def maximumLength(nums: List[int], k: int) -> int:
    count = [defaultdict(int) for _ in range(k + 1)]
    result = [0 for _ in range(k + 1)]

    for num in nums:
        for c in range(k, -1, -1):
            count[c][num] = (
                max(count[c][num], result[c - 1] if c > 0 else 0) + 1
            )
            result[c] = max(result[c], count[c][num])

    return max(result)


nums = [1, 2, 1, 1, 3]
k = 2
print(maximumLength(nums, k))  # 4

1884. Egg Drop With 2 Eggs and N Floors

887. Super Egg Drop

3448. Count Substrings Divisible By Last Digit

514. Freedom Trail

  • LeetCode | LeetCode CH (Hard)

  • Tags: string, dynamic programming, depth first search, breadth first search

3336. Find the Number of Subsequences With Equal GCD

1388. Pizza With 3n Slices

1900. The Earliest and Latest Rounds Where Players Compete

1883. Minimum Skips to Arrive at Meeting On Time

3343. Count Number of Balanced Permutations

3441. Minimum Cost Good Caption

3225. Maximum Score From Grid Operations

256. Paint House

265. Paint House II

3339. Find the Number of K-Even Arrays

568. Maximum Vacation Days

1692. Count Ways to Distribute Candies

2143. Choose Numbers From Two Arrays in Range

3269. Constructing Two Increasing Arrays

Comments