LeetCode-300. 最长递增子序列

约定不等于承诺〃 2024-03-26 21:12 80阅读 0赞

#### 目录 ####

*   *  动态规划

题目来源  
[300. 最长递增子序列][300.]

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]表示i之前包括i的以nums\[i\]结尾的最长递增子序列的长度

*  2.确定递推公式

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

if(nums[i]>nums[j]){
        
                       dp[i] = Math.max(dp[i],dp[j]+1);
                    }

*  3.dp\[i\]的初始化

每一个i，对应的dp\[i\]（即最长递增子序列）起始大小至少都是1.

*  4.确定遍历顺序

dp\[i\] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。  
j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。  
遍历i的循环在外层，遍历j则在内层，代码如下：

for(int i = 1;i<nums.length;i++){
        
                for(int j = 0;j<i;j++){
        
                    if(nums[i]>nums[j]){
        
                       dp[i] = Math.max(dp[i],dp[j]+1);
                    }
                }
                result = dp[i] > result?dp[i]:result; //取最长
            }

*  5.举例推导dp数组

输入：\[0,1,0,3,2\]，dp数组的变化如下：  
![在这里插入图片描述][7d48371b1df54b63ae92548572b1a25b.png]  
代码实现

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            int[] dp = new int[nums.length];
            for(int i=0;i<nums.length;i++){
        
                dp[i] = 1;
            }
            int result = 1;
            for(int i = 1;i<nums.length;i++){
        
                for(int j = 0;j<i;j++){
        
                    if(nums[i]>nums[j]){
        
                       dp[i] = Math.max(dp[i],dp[j]+1);
                    }
                }
                result = dp[i] > result?dp[i]:result; //取最长
            }
            return result;
        }
    }

![在这里插入图片描述][3f9900e12e5d43eeaa1b3d18f595d368.png]

[300.]: https://leetcode.cn/problems/longest-increasing-subsequence/
[7d48371b1df54b63ae92548572b1a25b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/60944ee77e7e4d9e940b90008e45a402.png
[3f9900e12e5d43eeaa1b3d18f595d368.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6825b00d93ba4036a414dabc44b7da27.png