动态规划下的最长递增子序列问题(LC)
发布时间
阅读量：
阅读量
问题
方法一：动态规划
定义一个数组dp[i]，用于记录以nums[i]作为结尾元素的最长递增子序列的长度（该子序列必须包含nums[i]），此时可以采用如下状态转移方程进行计算：
dp[i] = max\{dp[j] | 0 <= j < i 且nums[i]>nums[j]\} + 1
当所有位于i之前的元素nums[j]均大于当前元素nums[i]时，此时dp[i]的值将被设定为1。
public int lengthOfLIS(int[] nums) {
int len = nums.length;
int[] length = new int[len];
Arrays.fill(length,1);
for(int i = 0; i < len; i++){
for(int j = i + 1; j < len; j++){
if(nums[j] > nums[i]){全部评论 (0)
还没有任何评论哟~