LeetCode - 300. 最长递增子序列
题目描述
难度：中等
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
分析
读题，给定一个整数数组 nums ，求最长的升序子序列（子序列可以不连续）；
像这种最长，最优的问题一般都可以使用动态规划，大致可以理解为将要求的问题分解为一个一个子问题，通过求子问题的最优解来求原问题的最优解；
我们可以给定义状态 dp[i] 是以 nums[i] 这个元素结尾的最长升序子序列的长度，由于每个最长子序列的初始长度都是 1 也就是只有它本身，我们可以规定边界：dp[i] 的初始值为 1；
我们可以定义一个变量 j，它和变量 i 具有同样的意思 ( dp[ j ] 是以 nums[ j ] 这个元素结尾的最长升序子序列的长度) ，其中 0 ≤ j < i ，当 num[i] > num[j] 时可以认为 dp[i] = dp[j] + 1 (当前的子序列长度通过之前的子序列长度加 1 求得），然而 j 代表 i 之前的所有元素 且我们要取最优解也就是所有 dp[j] 中最长的，则有状态转移方程 dp[i] = max(dp[j]) + 1 （满足递增序列需要的判断条件: nums[i] > nums[j] );
代码：
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int max = 0;// 最长子序列长度
int[] dp = new int[nums.length]; // dp(i) 是以 nums[i] 结尾的最长递增子序列的长度
for (int i = 0; i < nums.length; 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); // dp[i] = max(dp[j]) + 1
}
}
// 每次都取出最长递增子序列的长度
max = Math.max(dp[i], max);
}
return max;
}
总结
第一次使用动态规划，思维还是比较模糊抽象，这个东西比较难理解，最开始自己用动态规划写的时候状态转移方程就写错了，导致最后全盘出错；
使用动态规划时能想出状态转移方程以及其条件，就已经参悟其奥妙一大半了，再接再厉！
岁月悠悠，衰微只及肌肤；热忱抛却，颓废必致灵魂