Dynamic Programming

ProblemGiven a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example 1: 1234Input: s = "leetcode", wordDict = ["leet","code"]Output: trueExplanation: Return true because "leetcode" can be segmented as "leet code". Example 2: 12345Input: s = "applepenap ...

ProblemYou are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: 0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1]. Example 1: 1234Input: nums = [2,3,1,1,4]Output: 2Explanation: T ...

ProblemYou are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Example 1: 1234Input: nums = [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: 1234Input: nums = [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter what. Its m ...

ProblemGiven an m x n binary matrix filled with 0‘s and 1‘s, find the largest square containing only 1‘s and return its area. Example 1: !https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg 123Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0& ...

123456789101112- [Leetcode]- [Python]- [medium]- [💡]- Math- Dynamic Programming- Combinatoricscover: /img/cover/leetcode.jpgcategories: Leetcode ProblemThere is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot c ...

leetcode62 ProblemGiven a triangle array, return the minimum path sum from top to bottom. For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row. Example 1: 123456789Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]Output: 11Explanation: The triangle looks like: 2 3 4 6 5 74 1 8 3The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above). Exa ...

可以先看看leetcode70 ProblemYou are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without ...

ProblemYou are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example 1: 123456Input: n = 2Output: 2Explanation: There are two ways to climb to the top.1. 1 step + 1 step2. 2 steps Example 2: 1234567Input: n = 3Output: 3Explanation: There are three ways to climb to the top.1. 1 step + 1 step + 1 step2. 1 step + 2 steps3. 2 steps + 1 step Constraints: 1 <= n <= 45 Solve用一般的**fibona ...

ProblemWe can scramble a string s to get a string t using the following algorithm: If the length of the string is 1, stop. If the length of the string is > 1, do the following: Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y. Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x. Apply step 1 recursively on each of the two substri ...

ProblemYou are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Example 1: 12345Input: prices = [7,1,5,3,6,4]Output: 5Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.Note that buyi ...