Skip to content

DP 1D

Table of Contents

2944. Minimum Number of Coins for Fruits

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, queue, heap priority queue, monotonic queue

2140. Solving Questions With Brainpower

2140. Solving Questions With Brainpower - Python Solution
from functools import cache
from typing import List


# Memoization
def mostPoints(questions: List[List[int]]) -> int:
    @cache
    def dfs(i: int) -> int:
        if i >= len(questions):
            return 0
        return max(dfs(i + 1), dfs(i + questions[i][1] + 1) + questions[i][0])

    return dfs(0)


if __name__ == "__main__":
    questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
    print(mostPoints(questions))  # 5

983. Minimum Cost For Tickets

983. Minimum Cost For Tickets - Python Solution
from typing import List


# DP
def mincostTickets(days: List[int], costs: List[int]) -> int:
    last = days[-1]
    dayset = set(days)
    dp = [0 for _ in range(last + 1)]

    for i in range(1, last + 1):
        if i not in dayset:
            dp[i] = dp[i - 1]
        else:
            dp[i] = min(
                dp[i - 1] + costs[0],
                dp[max(0, i - 7)] + costs[1],
                dp[max(0, i - 30)] + costs[2],
            )

    return dp[last]


days = [1, 4, 6, 7, 8, 20]
costs = [2, 7, 15]
print(mincostTickets(days, costs))  # 11

2901. Longest Unequal Adjacent Groups Subsequence II

3144. Minimum Substring Partition of Equal Character Frequency

871. Minimum Number of Refueling Stops

2896. Apply Operations to Make Two Strings Equal

2167. Minimum Time to Remove All Cars Containing Illegal Goods

2188. Minimum Time to Finish the Race

3389. Minimum Operations to Make Character Frequencies Equal

  • LeetCode | LeetCode CH (Hard)

  • Tags: hash table, string, dynamic programming, counting, enumeration

3205. Maximum Array Hopping Score I

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, stack, greedy, monotonic stack

1259. Handshakes That Don't Cross

Comments