Dp

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score. ...

Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing. Example 1: Input: nums = [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: nums = [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5. Constraints: ...

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time). Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps. Since the answer may be too large, return it modulo 109 + 7. ...

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of arithmetic subarrays of nums. A subarray is a contiguous subsequence of the array. Example 1: Input: nums = [1,2,3,4] Output: 3 Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself. Example 2: Input: nums = [1] Output: 0 Constraints: ...

Wine Selling Problem Problem statement: Given n wines in a row, with integers denoting the cost of each wine respectively. Each year you can sell the first or the last wine in the row. Let the initial profits from the wines be P1, P2, P3…Pn. In the Yth year, the profit from the ith wine will be Y*P[i]. The goal is to calculate the maximum profit that can be earned by selling all the wines. ...

343. Integer Break Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get. Example 1: Input: n = 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1. Example 2: Input: n = 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Constraints: ...

221. Maximal Square Given 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: Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4 Example 2: Input: matrix = [["0","1"],["1","0"]] Output: 1 Example 3: Input: matrix = [["0"]] Output: 0 Constraints: m == matrix.length n == matrix[i].length 1 <= m, n <= 300 matrix[i][j] is ‘0’ or ‘1’. Solution class Solution { public int maximalSquare(char[][] matrix) { int n = matrix.length; int m = matrix[0].length; int[][] dp = new int[n][m]; int max = 0; for (int j = 0; j < m; j++) { dp[0][j] = matrix[0][j] == '0' ? 0 : 1; max = Math.max(dp[0][j], max); } for (int i = 0; i < n; i++) { dp[i][0] = matrix[i][0] == '0' ? 0: 1; max = Math.max(dp[i][0], max); } for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (matrix[i][j] == '0') { dp[i][j] = 0; } else { dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1; } max = Math.max(dp[i][j], max); } } return max * max; } int min(int a, int b, int c) { return Math.min(a, Math.min(b,c)); } }

472. Concatenated Words Given an array of strings words (without duplicates), return all the concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array. Example 1: Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat". Example 2: Input: words = ["cat","dog","catdog"] Output: ["catdog"] Constraints: ...

93. Restore IP Addresses Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order. A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses and “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses. ...

139. Word Break Given 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: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Example 2: Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false Constraints: ...