300. 最长递增子序列
利用动态规划解题 dp[0] = 1 定义为 第一个元素的包括该元素的最长子串为1;
状态转移方程:
遍历 m m<n 如果nums[m]<nums[n] dp[n] =Math.max(dp[n],dp[m]+1);
class Solution {
/**
动态规划
*/
public int lengthOfLIS(int[] nums) {
int res =1;
int len = nums.length;
// 边界条件
if(len == 0) return 0;
int[] dp = new int[len];
dp[0] = 1;
for(int i =1;i<len;i++){
// 开始默认 该位置为独立字串
dp[i] = 1;
for(int j = 0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
// 一次遍历记录最大字串
res = Math.max(res,dp[i]);
}
return res;
}
}
变形
673. 最长递增子序列的个数
难度增加,用额外的record数组记录路径数。
class Solution {
/**
*/
public int findNumberOfLIS(int[] nums) {
int res =0;
int maxn =0;
int len = nums.length;
if(len == 0)return 0;
int[] dp = new int[len];
int[] record = new int[len];
dp[0] = 1;
//默认路径为1
record[0] = 1;
// 上一个题可以从 1开始,为什么这个就不可以从1开始了呢?
for(int i =0;i<len;i++){
// 这里res是通过一次遍历累加的 如果用1 在执行[2,2,2,2,2] 的时候就会漏掉第一个
dp[i] =1;
record[i] = 1;
for(int j = 0;j<i;j++){
if(nums[j]<nums[i]){
if(dp[j]+1>dp[i]){
dp[i] = dp[j]+1;
// 如果可以从j到i那么他为 通往最长路径的路径,集成它的路径数
record[i] = record[j];
}else if(dp[j]+1==dp[i]){
// 如果数量+1恰好与当前dp[i]相同。那么就发现额外了路径
record[i]+=record[j];
}
}
}
if(dp[i]>maxn){
maxn = dp[i];
res = record[i];
}else if(dp[i] == maxn){
res+=record[i];
}
}
return res;
}
}