- 问题：原字符串拆分成回文串的最小切割数
设：f(i)是从i开始到结尾的最小切割数（从后->前遍历）
则：f(i)=min{f(j+1)+1},i≤j<n （其中，s[i] =s[j], i和j之间构成了一个小回文序列）
public int minCut(String s) {
if(s == null || s.length() <= 1)
return 0;
int len = s.length();
boolean[][] p = new boolean[len][len];
int[] dp = new int[len+1];
for(int i = 0 ; i < len; i++){
for(int j =0; j<len;j++){
p[i][j] = false;
}
}
for(int i = len; i >=0; i--){
dp[i] = len-i-1;
}
for(int i = len-1; i >=0 ;i--){
for(int j=i; j <len;j++){
if(s.charAt(i) == s.charAt(j)){
if(j-i<=1 || p[i+1][j-1] == true){
p[i][j] = true;
dp[i] = Math.min(dp[i] , dp[j+1] +1 );
}
}
}
}
return dp[0];
}
- 乘积最大子序列：给定一个数组，求其中连续乘积值最大的结果
纠结点：之前的最大值，可能因为×负数，就变成最小；之前的最小值，可能因为×负数，变最大。
设：f[i]表示子数组[0, i]范围内的最大子数组乘积，g[i]表示子数组[0, i]范围内的最小子数组乘积
则：f[i] = f[i-1] * nums[i]，g[i-1] * nums[i]，和nums[i] 中的最大值；
g[i] = f[i-1] * nums[i]，g[i-1] * nums[i]，和nums[i] 中的最小值；
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int maxProduct(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return 0;
}
int minPre = nums[0], maxPre = nums[0];
int max = nums[0], min = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; i ++) {
max = Math.max(nums[i], Math.max(maxPre * nums[i], minPre * nums[i]));
min = Math.min(nums[i], Math.min(maxPre * nums[i], minPre * nums[i]));
res = Math.max(res, max);
maxPre = max;
minPre = min;
}
return res;
}
}
- 整数拆分：将一个数字拆分成多个，求拆分后的最大乘积
设：f[n] 表示数字为 n 时的最优值，
则： f[n] =max(n , [ max(i, f[i]) * max(j, f[j]) ] ) 其中 i + j == n
public int integerBreak(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i<=n;i++){
for(int j =1; j <i; j++){
dp[i] = Math.max(dp[i],Math.max(j, dp[j]) * Math.max((i-j) , dp[i-j])) ;
}
}
return dp[n];
}
- 递增子序列的最长长度
设： f[i]是以i为结尾的 最长递增子序列的长度
则： f[i] = max{f[i] , f[j] +1 } (其中 j 需要满足： nums[j]< nums[i])
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
if(nums.length == 1)
return 1;
// 声明：dp数组
int[] dp = new int[nums.length];
for(int i =0; i < dp.length; i++){
dp[i] = 1;
}
// 递归计算
int max_len=0;
for(int i=1; i< nums.length; i++){
// 需要找到 在i前面，并且比i小的j
for(int j = 0; j< i; j++){
if(nums[j] < nums[i])
{
dp[i] = Math.max(dp[i] , dp[j] + 1);
}
}
if(dp[i] > max_len)
max_len = dp[i];
}
return max_len;
}
- 找出：递增子序列最长的 子序列个数
设：len[i]为[0,i]之间，递增子序列的最长长度; cnt[i]为当len[i]当前最长时，可达到这一长度的序列个数
则：
从前->后遍历i 从前->i遍历j:
若：nums[j] < nums[i]: 若len[i] < len[j] +1,则len[i] = len[j] +1且 cnt[i] = cnt[j];
若len[i] = len[j] +1,则cnt[i] += cnt[j]
int findNumberOfLIS(vector<int>& nums) {
int res = 0, mx = 0, n = nums.size();
vector<int> len(n, 1), cnt(n, 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] <= nums[j]) continue;
if (len[i] == len[j] + 1) cnt[i] += cnt[j];
else if (len[i] < len[j] + 1) {
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
if (mx == len[i]) res += cnt[i];
else if (mx < len[i]) {
mx = len[i];
res = cnt[i];
}
}
return res;
}
- 矩阵中的最长递增路径
设：dp[i][j]是以(i,j)开始的最长路径
则：dp[i][j] = max{dp[i+-1][j+-1]} +1（[i+-1][j+-1]代表了(i,j)邻居节点里 数值大于matrix(i,j)本身的邻居 的最大路径）
int[][] direction = {{0,-1},{0,1},{1,0},{-1,0}};
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int [m][n]; // 记录：以该点为起点时，最长路径的长度
int max = 1;
for(int i =0 ; i < m; i++){
for(int j =0 ; j < n; j++){
int res = dfs(matrix, dp, i, j);
max = Math.max(max, res);
}
}
return max;
}
public int dfs(int[][] matrix,int[][] dp, int cur_x, int cur_y){
if(dp[cur_x][cur_y] !=0)
return dp[cur_x][cur_y];
int max = 1;
for(int i =0 ;i < 4; i ++){
int add_x = direction[i][0];
int add_y = direction[i][1];
int x = add_x + cur_x;
int y = add_y + cur_y;
if(x >=0 && x< matrix.length && y >=0 && y< matrix[0].length && matrix[x][y] > matrix[cur_x][cur_y] ){
dp[x][y] = dfs(matrix, dp, x, y);
max = Math.max(dp[x][y] +1 , max);
}
}
return max;
}
- 最长匹配括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
设：dp[i]代表了从index=0开始，匹配到index=i, 最长匹配括号的长度
则：if(s[i] == '(') dp[i]=0
if(s[i]==')')
if(s[i-1]=='(') 则dp[i] = 2+dp[i-2]
else if(i-dp[i-1]-1>0 && s[i-dp[i-1]-1]=='(') // 把紧挨着、之前匹配的都掠过去，看上一次未匹配的字母是否为左括号
则dp[i]=dp[i-1]+2 + dp[i-dp[i-1]-2]
public int longestValidParentheses(String s) {
int[] dp=new int[s.length()];
int max=0;
for (int i=1;i<s.length();i++){
if (s.charAt(i)=='(') dp[i]=0;
else{
if (s.charAt(i-1)=='(') dp[i]=2+(i==1?0:dp[i-2]);
else {
if ((i-dp[i-1]-1>-1)&&s.charAt(i-dp[i-1]-1)=='(')
dp[i]=dp[i-1]+(i-dp[i-1]-1==0?0:dp[i-dp[i-1]-2])+2;
}
}
max=Math.max(max,dp[i]);
}
return max;
}
- Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
设：dp[i] 代表数字之和=i时的组合方法数
则：dp[i]= nums[0] 与 dp[i-nums[0]]的结合数 + nums[1] 与 dp[i-nums[1]]的结合数+ nums[2] 与 dp[i-nums[2]]的结合数
=dp[i-nums[0]] + dp[i-nums[1]] + ……
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;
// 外层遍历：sum总和
for(int sum=1;sum<=target;sum++){
// 内层遍历：各个num数字
for(int num: nums){
if(num<=sum){
dp[sum] += dp[sum-num];
}
}
}
return dp[target];
}
- Distinct Subsequences II
问题：
Given a string S, count the number of distinct, non-empty subsequences of S .
Since the result may be large, return the answer modulo 10^9 + 7.
Input: s = "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
截屏2021-12-07 下午5.13.37.png
class Solution {
public int distinctSubseqII(String S) {
int MOD = 1_000_000_007;
int N = S.length();
int[] dp = new int[N+1];
dp[0] = 1;
int[] last = new int[26];
Arrays.fill(last, -1);
for (int i = 0; i < N; ++i) {
int x = S.charAt(i) - 'a';
dp[i+1] = dp[i] * 2 % MOD;
if (last[x] >= 0)
dp[i+1] -= dp[last[x]];
dp[i+1] %= MOD;
last[x] = i;
}
dp[N]--;
if (dp[N] < 0) dp[N] += MOD;
return dp[N];
}
}
- Maximum Length of Repeated Subarray
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
分析：dp[i][j] : max lenth of common subarray start at a[i] & b[j];
则dp[i][j] = a[i] == b[j] ? 1 + dp[i + 1][j + 1] : 0;
public int findLength(int[] A, int[] B) {
int m = A.length,n=B.length;
int max = 0;
int[][]dp = new int[m+1][n+1];
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(A[i]==B[j]){
dp[i][j] = 1+dp[i+1][j+1];
max = Math.max(dp[i][j], max);
}
}
}
return max;
}
- Continuous Subarray Sum
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to nk where n is also an integer.
Example 1:
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
分析：重点是下面的数学思想
(a+(nx))%x is same as (a%x)
For e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42] and the remainders are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number which is multiple of the k.
代码：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0,-1);
int remainderSum = 0;
for(int i=0;i<nums.length;i++){
int num = nums[i];
remainderSum += num;
if(k!=0)
remainderSum = remainderSum%k;
Integer lastPos = map.get(remainderSum);
if(lastPos != null){
if(i-lastPos >= 2)
return true;
}else{
map.put(remainderSum,i);
}
}
return false;
}
}
- Longest Palindromic Substring——最长回文子串
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
分析：dp(i, j) represents whether s(i ... j) can form a palindromic substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a palindromic substring
代码：
public String longestPalindrome(String s) {
String res = "";
int len = s.length();
boolean[][] dp = new boolean[len][len];
for(int i=len-1;i>=0;i--){
for(int j=i; j<len; j++){
if(s.charAt(i) == s.charAt(j) && (j-i<3 || dp[i+1][j-1])){
dp[i][j] = true;
if( j-i+1 > res.length())
res = s.substring(i,j+1);
}
}
}
return res;
}
- Maximal Square
Share
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
分析：dp[i][j] 代表在以i, j这一格为右下角的正方形边长。
如果这一格的值也是1，那这个正方形的边长就是他的上面，左手边，和斜上的值的最小边长 +1。因为如果有一边短了缺了，都构成不了正方形
public int maximalSquare(char[][] matrix) {
if(matrix.length == 0 )
return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m+1][n+1];
int max_len = 0;
for(int i=1;i<=m;i++){
for(int j=1; j<=n; j++){
if(matrix[i-1][j-1] == '1'){
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]), dp[i-1][j-1]) + 1;
if(dp[i][j]>max_len)
max_len = dp[i][j];
}
}
}
return max_len * max_len;
}
- Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
分析：
The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).
left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row
right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'
public int maximalRectangle(char[][] matrix) {
if(matrix.length == 0) return 0;
int m=matrix.length,n=matrix[0].length;
int[] height = new int[n], left = new int[n], right = new int[n];
int max_range = 0;
Arrays.fill(right,n);
for(int i=0;i<m;i++){
// 计算height
for(int j=0; j<n; j++){
if(matrix[i][j] == '1') height[j]++;
else height[j] =0;
}
// 计算left, → 遍历
int cur_left = 0;
for(int j=0; j<n; j++){
if(matrix[i][j] == '1') left[j]=Math.max(left[j], cur_left);
else{left[j]=0; cur_left=j+1;}
}
// 计算right, ← 遍历
int cur_right = n;
for(int j=n-1; j>=0; j--){
if(matrix[i][j] == '1') right[j]=Math.min(right[j], cur_right);
else{right[j]=n; cur_right=j;}
}
for(int j=0; j<n; j++){
int range = (right[j]-left[j])*height[j];
max_range = Math.max(range, max_range);
}
}
return max_range;
}
- Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
例如：
Input: [2,1,5,6,2,3]
image
Output: 10
public int largestRectangleArea(int[] heights) {
if(heights == null || heights.length == 0 ) return 0;
int m = heights.length;
int[] left = new int[m], right = new int[m];
// 构建left数组，left[i]记录的是i最左侧的、高度>=i的
left[0] = 0;
for(int i=1;i<m;i++){
int p=i-1;
while(p>=0 && heights[p]>=heights[i]){
p = left[p]-1;
}
left[i]=p+1; // +1：当前p的高度一定<i, 所以+1，找刚好最左、>i的那个
}
// 构建right数组，right[i]记录的是i最右侧的、高度>=i的
right[m-1]=m-1;
for(int i=m-2;i>=0;i--){
int p=i+1;
while(p<=m-1 && heights[p]>=heights[i]){
p = right[p]+1;
}
right[i]=p-1;
}
// 计算面积
int max_area = 0;
for(int i=0;i<m;i++){
int cur_area = heights[i] * (right[i]-left[i]+1);
max_area = Math.max(max_area, cur_area);
}
return max_area;
}
// 第二种方法：
// Pruning optimize
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int res = 0;
for (int i = 0; i < height.size(); ++i) {
if (i + 1 < height.size() && height[i] <= height[i + 1]) {
continue;
}
int minH = height[i];
for (int j = i; j >= 0; --j) {
minH = min(minH, height[j]);
int area = minH * (i - j + 1);
res = max(res, area);
}
}
return res;
}
};
- 解码方法
问题：
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
思路：
此题和爬楼梯是同一个类型的问题，难点在于其添加了许多限制条件，只要避开限制条件就可以完美解题了
每次递进，可以选取一个数也可以选取两个数：
s[i] != '0'
如果 s[i-1]s[i] <= 26, 则 dp[i] = dp[i-1] + dp[i-2]
如果 s[i-1]s[i] > 26, 则 dp[i] = dp[i-1], 这是因为 s[i-1]s[i] 组成的两位数无法翻译
s[i] == '0'
如果 s[i-1]s[i] <= 26, 则 dp[i] = dp[i-2], 这是因为 s[i] 无法翻译
还有一些情景直接使得整个序列无法被翻译：
相邻的两个 ‘0’
以 ‘0’ 结尾的大于 26 的数字
去除这些限制条件，此题就是爬楼梯的问题了，一次可以爬一步，也可以爬两步，问有多少中方式到达终点。
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if not s or s[0] == '0': # 基本情况，直接返回 0
return 0
dp = [None] * len(s) # 构建 dp 数组
dp[0] = 1 # 只有一个数时肯定为 1
if len(s) > 1: # 为 dp[1] 填充值
if s[1] == '0': # s[i] 为 ‘0’ 时
if int(s[0:2]) <= 26: # 截取前两数，判断是否小于或等于 26
dp[1] = 1 # 因为 s[i] 为 ‘0’ 所以 dp[1] 只有 1 种可能
else:
return 0 # 比如 60 , 此时该序列无法翻译
else: # s[i] 不为 ‘0’ 时
if int(s[0:2]) <= 26:
dp[1] = 2 # 比如 16，有两种翻译结果
else:
dp[1] = 1 # 比如 27，只有一种结果
else: # 只有一个数
return 1
for i in range(2, len(s)): # 从 2 开始
if s[i] == '0': # s[i] 为 ‘0’ 时
if s[i-1] == '0': # 前一个为 ‘0’
return 0 # 无解
else: # 前一个不为 ‘0’
if int(s[i-1:i+1]) <= 26: # s[i-1] 和 s[i] 组成的数 <= 26
dp[i] = dp[i-2]
else:
return 0
else: # s[i] 不为 ‘0’
if s[i-1] == '0': # 前一个为 ‘0’
dp[i] = dp[i-1]
else: # 前一个不为 ‘0’
if int(s[i-1:i+1]) <= 26: # s[i-1] 和 s[i] 组成的数 <= 26
dp[i] = dp[i-1] + dp[i-2]
else: # s[i-1] 和 s[i] 组成的数 > 26
dp[i] = dp[i-1]
return dp[len(s) - 1]
