Dynamic Programming

ProblemGiven an integer array nums, return the length of the longest strictly increasing subsequence . Example 1: 1234Input: nums = [10,9,2,5,3,7,101,18]Output: 4Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Example 2: 123Input: nums = [0,1,0,3,2,3]Output: 4 Example 3: 123Input: nums = [7,7,7,7,7,7,7]Output: 1 Constraints: 1 <= nums.length <= 2500 104 <= nums[i] <= 104 Follow up: Can you come up with an algorithm that runs in O(n log( ...

ProblemYou are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Example 1: 1234Input: coins = [1,2,5], amount = 11Output: 3Explanation: 11 = 5 + 5 + 1 Example 2: 123Input: coins = [2], ...

ProblemYou are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve. Example 1: 123456Input: prices = [7,1,5,3,6,4]Output: 7Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.Then buy ...

ProblemGiven a string s, return the longest palindromic substring in 1s . Example 1: 1234Input: s = "babad"Output: "bab"Explanation: "aba" is also a valid answer. Example 2: 123Input: s = "cbbd"Output: "bb" Constraints: 1 <= s.length <= 1000 s consist of only digits and English letters. Solve123456789101112131415161718192021class Solution: def longestPalindrome(self, s: str) -> str: res = "" for i in range ...

ProblemA path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. Example 1: !https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg 1234Input: root = [1,2,3]Output: 6 ...

ProblemGiven two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not). Example 1: 123Input: s = "abc", t = "ahbgdc"Output: true Example 2: 123Input: s = "axc ...

ProblemGiven a binary array nums, you should delete one element from it. Return the size of the longest non-empty subarray containing only 1‘s in the resulting array. Return 0 if there is no such subarray. Example 1: 1234Input: nums = [1,1,0,1]Output: 3Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's. Example 2: 1234Input: nums = [0,1,1,1,0,1,1,0,1]Output: 5Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest suba ...

ProblemGiven an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Example 1: 1234Input: intervals = [[1,2],[2,3],[3,4],[1,3]]Output: 1Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping. Example 2: 1234Input: intervals = [[1,2],[1,2],[1,2]]Output: 2Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping. ...

ProblemThe thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police ...

ProblemGiven an integer array nums, find the subarray with the largest sum, and return its sum . Example 1: 1234Input: nums = [-2,1,-3,4,-1,2,1,-5,4]Output: 6Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: 1234Input: nums = [1]Output: 1Explanation: The subarray [1] has the largest sum 1. Example 3: 1234Input: nums = [5,4,-1,7,8]Output: 23Explanation: The subarray [5,4,-1,7,8] has the largest sum 23. Constraints: 1 <= nums.length <= 10^5 10^4 <= nums[i] <= 1 ...