做网站的版权问题,建e室内设计网贴图,单页网站案例分析,电子商务网站建设的书子序列问题可以按照动态规划的思想去写。
子序列问题类型
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。
例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
写法思路
创建两层for循环…子序列问题可以按照动态规划的思想去写。
子序列问题类型
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。
例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
写法思路
创建两层for循环外层为for(int i0;in;i);内层为for(int j0;ji;j)。
然后就写转移方程即可。
例题NO.300. 最长递增子序列
题目 链接
https://leetcode.cn/problems/longest-increasing-subsequence/description/
代码:
class Solution {// 状态表示 以i结束的序列最长严格递增序列的长度 public int lengthOfLIS(int[] nums) {int nnums.length;int[] dpnew int[n];// 初始化for(int i0;in;i) dp[i]1;int ret1;for(int i0;in;i){for(int j0;ji;j){// 转移方程if(nums[i]nums[j]){dp[i]Math.max(dp[i],dp[j]1);}}retMath.max(ret,dp[i]);}return ret;}
}状态表示 以i结束的序列最长严格递增序列的长度转移方程 长度为1时dp[i]1长度大于1时满足(nums[i]nums[j]则dp[i]Math.max(dp[i],dp[j]1);初始化因为长度1所以每一个以i结尾的序列最小长度为1于是令全数组长度为1.填表顺序 从左往右依次填写。总结
子序列问题包含子数组问题这类问题是动态规划的一种形式当然也可以用其他方法写只不过是变成了双层for循环。
