Skip to content

DP Other DP

Table of Contents

1387. Sort Integers by The Power Value

823. Binary Trees With Factors

940. Distinct Subsequences II

135. Candy

"""
-   Return the minimum number of candies you must give.
"""

from typing import List


# Greedy
def candy(ratings: List[int]) -> int:
    # TC: O(n)
    # SC: O(n)
    n = len(ratings)

    if n <= 1:
        return n

    candy = [1 for _ in range(n)]

    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candy[i] = candy[i - 1] + 1

    for j in range(n - 2, -1, -1):
        if ratings[j] > ratings[j + 1]:
            candy[j] = max(candy[j], candy[j + 1] + 1)

    return sum(candy)


ratings = [1, 0, 2]
print(candy(ratings))  # 5

650. 2 Keys Keyboard

638. Shopping Offers

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Backtracking, Bit Manipulation, Memoization, Bitmask

467. Unique Substrings in Wraparound String

2262. Total Appeal of A String

828. Count Unique Characters of All Substrings of a Given String

2746. Decremental String Concatenation

2930. Number of Strings Which Can Be Rearranged to Contain Substring

1569. Number of Ways to Reorder Array to Get Same BST

  • LeetCode | 力扣

  • Tags: Array, Math, Divide And Conquer, Dynamic Programming, Tree, Union Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree

818. Race Car

920. Number of Music Playlists

1388. Pizza With 3n Slices

1987. Number of Unique Good Subsequences

903. Valid Permutations for DI Sequence

1896. Minimum Cost to Change the Final Value of Expression

1531. String Compression II

964. Least Operators to Express Number

1787. Make the XOR of All Segments Equal to Zero

2060. Check if an Original String Exists Given Two Encoded Strings

2809. Minimum Time to Make Array Sum At Most x

3299. Sum of Consecutive Subsequences

2189. Number of Ways to Build House of Cards

2597. The Number of Beautiful Subsets

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Math, Dynamic Programming, Backtracking, Sorting, Combinatorics

#include <functional>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    int beautifulSubsets(vector<int>& nums, int k) {
        int res = 0;
        unordered_map<int, int> cnt;

        auto dfs = [&](auto&& self, int i) -> void {
            if (i == (int)nums.size()) {
                res++;
                return;
            }
            self(self, i + 1);  // Skip nums[i]
            int x = nums[i];
            if (cnt[x - k] == 0 && cnt[x + k] == 0) {
                cnt[x]++;
                self(self, i + 1);  // Include nums[i]
                cnt[x]--;           // Backtrack
            }
        };

        dfs(dfs, 0);

        return res - 1;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3, 4};
    int k = 1;
    cout << sol.beautifulSubsets(nums, k) << endl;
    return 0;
}

2638. Count the Number of K-Free Subsets

Comments