- 问题：原字符串拆分成回文串的最小切割数
设：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(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;
}
- 最长匹配括号
设：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;
}
- Profitable schema——计算方法的个数（注意不是计算最大收益，而是能达到这种收益的配置方案有几个？）
Input: G = 5, P = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation:
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.
public int profitableSchemes(int G, int P, int[] group, int[] profit) {
int task = group.length;
int MOD = 1000000007;
int[][] dp = new int[G+1][P+1]; // 选取 j 个人员，获得 k 的收益 的方法数。
dp[0][0] = 1;
// 正序遍历项目（只有 被隐匿掉的变量 是正序的）
for(int i=1;i<=task; i++){
int g=group[i-1]; // 该项目用人
int p=profit[i-1]; // 该项目利润
// 倒序遍历人
for(int j=G;j>=g;j--){
for(int k=P;k>=0;k--){
dp[j][k] = dp[j][k] + // 不用k项目时的schema个数
(j>=g? dp[j-g][Math.max(0, k-p)]:0); // 利用k项目的schema个数
dp[j][k] = dp[j][k]%MOD;
}
}
}
long res = 0L;
for(int i=0;i<=G;i++){
res = (res+dp[i][P])%MOD;
}
return (int)res;
}
- 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
思路：简历一个26位的数组endCharCount，endCharCount[0]记录在字符串S中 以'a'为结尾的子串个数
endCharCount[0] = endCharCount[*] + 1
解释：+1，代表了加上'a'本身
public int distinctSubseqII(String S) {
int[] endCharCount = new int[26]; // 以各个字符结尾的子串个数
int MOD = 1000000007;
// 外层遍历： 字符串的各个字符
for(char ch: S.toCharArray()){
// 内层遍历：已经找到的 （以各个字符结尾的子串个数）
int cur_sum = 0;
for(int tmpCount: endCharCount){
cur_sum = (cur_sum+ tmpCount)%MOD;
}
endCharCount[ch-'a'] = cur_sum + 1;
}
int res=0;
for(int tmpCount: endCharCount){
res = (res+tmpCount)%MOD;
}
return res;
}
网友评论