interval-dp | brain

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1000: Minimum Cost to Merge Stones

Problem Restatement We are given an array stones . The i th value tells us how many stones are in pile i . We are also given an integer k . In one move, we must merge exactly k consecutive piles into one pile. The cost of that move is the total number of stones in those k piles. We need to return the minimum total cost to merge all...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 664: Strange Printer

Problem Restatement We are given a string s . There is a strange printer with two rules: Rule Meaning Same character only In one turn, the printer can print only one repeated character Overwrite allowed A later turn can cover characters printed earlier The printer can choose any continuous segment of the string in one turn. Return the minimum number of turns needed to print the whole string. For example,...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 546: Remove Boxes

Problem Restatement We are given an array boxes . Each integer represents the color of one box. In one move, we can remove a continuous group of boxes with the same color. If the group has k boxes, we gain: k * k points. After removing boxes, the remaining boxes close the gap. We repeat this until no boxes remain. We need to return the maximum score possible. The official...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 516: Longest Palindromic Subsequence

Problem Restatement We are given a string s . We need to return the length of the longest subsequence of s that is also a palindrome. A subsequence is made by deleting zero or more characters without changing the order of the remaining characters. A palindrome reads the same forward and backward. The official problem asks for the length of the longest palindromic subsequence in s . The constraints are...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 877: Stone Game

Problem Restatement Alice and Bob play a game with an even number of stone piles arranged in a row. Each pile has a positive number of stones. Alice moves first. On each turn, a player must take one entire pile from either the left end or the right end of the row. The game ends when all piles are taken. The player with more stones wins. The total number of...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 375: Guess Number Higher or Lower II

Problem Restatement We are playing a guessing game. A number is picked from: 1 to n Each time we guess a number x : Result Cost Guess is correct Pay 0 Guess is wrong Pay x dollars If the guess is wrong, we are told whether the hidden number is higher or lower, then we continue guessing in the remaining range. We need to return the minimum amount of money...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 471: Encode String with Shortest Length

Problem Restatement We are given a non-empty lowercase string s . We need to encode it so that the encoded string has the shortest possible length. The encoding rule is: k[encoded_string] where encoded_string is repeated exactly k times. If encoding does not make the string shorter, we should keep the original string. If there are multiple shortest answers, returning any one of them is allowed. The input length is at...