DP Multi-Dimensional¶
Table of Contents¶
- 2400. Number of Ways to Reach a Position After Exactly k Steps (Medium)
- 1824. Minimum Sideway Jumps (Medium)
- 3332. Maximum Points Tourist Can Earn (Medium)
- 2370. Longest Ideal Subsequence (Medium)
- 3176. Find the Maximum Length of a Good Subsequence I (Medium)
- 1269. Number of Ways to Stay in the Same Place After Some Steps (Hard)
- 3250. Find the Count of Monotonic Pairs I (Hard)
- 3218. Minimum Cost for Cutting Cake I (Medium)
- 3122. Minimum Number of Operations to Satisfy Conditions (Medium)
- 576. Out of Boundary Paths (Medium)
- 403. Frog Jump (Hard)
- 1223. Dice Roll Simulation (Hard)
- 1320. Minimum Distance to Type a Word Using Two Fingers (Hard)
- 3366. Minimum Array Sum (Medium)
- 1575. Count All Possible Routes (Hard)
- 3154. Find Number of Ways to Reach the K-th Stair (Hard)
- 2318. Number of Distinct Roll Sequences (Hard)
- 1444. Number of Ways of Cutting a Pizza (Hard)
- 3320. Count The Number of Winning Sequences (Hard)
- 3429. Paint House IV (Medium)
- 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons (Hard)
- 3193. Count the Number of Inversions (Hard)
- 629. K Inverse Pairs Array (Hard)
- 1079. Letter Tile Possibilities (Medium)
- 1866. Number of Ways to Rearrange Sticks With K Sticks Visible (Hard)
- 2312. Selling Pieces of Wood (Hard)
- 3177. Find the Maximum Length of a Good Subsequence II (Hard)
- 1884. Egg Drop With 2 Eggs and N Floors (Medium)
- 887. Super Egg Drop (Hard)
- 3448. Count Substrings Divisible By Last Digit (Hard)
- 514. Freedom Trail (Hard)
- 3336. Find the Number of Subsequences With Equal GCD (Hard)
- 1388. Pizza With 3n Slices (Hard)
- 1900. The Earliest and Latest Rounds Where Players Compete (Hard)
- 1883. Minimum Skips to Arrive at Meeting On Time (Hard)
- 3343. Count Number of Balanced Permutations (Hard)
- 3441. Minimum Cost Good Caption (Hard)
- 3225. Maximum Score From Grid Operations (Hard)
- 256. Paint House (Medium) 👑
- 265. Paint House II (Hard) 👑
- 3339. Find the Number of K-Even Arrays (Medium) 👑
- 568. Maximum Vacation Days (Hard) 👑
- 1692. Count Ways to Distribute Candies (Hard) 👑
- 2143. Choose Numbers From Two Arrays in Range (Hard) 👑
- 3269. Constructing Two Increasing Arrays (Hard) 👑
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¶
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¶
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¶
2318. Number of Distinct Roll Sequences¶
1444. Number of Ways of Cutting a Pizza¶
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¶
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