300. 最长上升子序列

300. 最长上升子序列

1.想法

最开始我想用回溯法做,但是发现整个算法的时间复杂度非常大

• 1.回溯法:

  
  image.png
  

  每一层的选择都不影响上一层的选择,遍历所有情况最终得到所有的结果,找出一直递增的结果

  
  image.png
  以题目为例:

1. 如果选择了10,那么接下来到9就判断是否能选,因为9<10所以不能选,只能再看下一个,直到101,大于10,所以可以选择,那么选择101,计数+1,并且最大的数更换成101
2. 如果不选择10,那么9就可以选择,选择9的情况下,暂时最大数是9,那么同样的道理到101发现可以更新
3. 重复以上过程,直到选择的次数达到数组长度,递归结束

总结:由于每个数都有两次的选择机会,所以时间复杂度为O(2^n).不满足条件,所以必须要降低时间复杂度:降低时间复杂度的方法,以空间换时间 能以空间换时间的1.直接的容器存储 不涉及递归或者迭代的过程 2.涉及递归或者迭代的过程 很明显贪心法无法直接完成这个过程,那么利用动态规划

2.动态规划

image.png

那么按照动态规划的一般过程进行处理就可以了

1.建模

①解:<max>代表了最长的那么解
②目标函数:max = max(f(0),f(1),...f(n-1))

③约束条件:nums[n]>nums[j] 其中j<n;

2.子问题优化

1.当n=0时,f(0)=1;
2.当nums[i]>nums[j]&&i>j时:f[i] = f[j]+1
3.当nums[i]<nums[j]&&i<j时,跳过

3.归结公式

就是说:找出前面所有数字比现数字小且其增长序列是最长的

2.代码:

1.回溯法:(超时)

 int maxCount = 0;
    public int lengthOfLIS(int[] nums) {
      MyBackTracking(nums,0,0,Integer.MIN_VALUE); //回溯开始
      return maxCount;
    }

    private void MyBackTracking(int[] nums, int count, int size,int max) {
        if(count == nums.length){   //选择完毕
            if(size>maxCount){
                maxCount  = size;
            }
        }else{
            if(nums[count]>max){   //若可选择,则选择,并更新最新的长度和最大值
                MyBackTracking(nums,count+1,size+1,nums[count]);
            }
            MyBackTracking(nums,count+1,size,max); //不可选择或者选择另一种
        }
    }

回溯法

2.动态规划:

    public int lengthOfLIS(int[] nums) {
        int max = 0;
        int[] f = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && f[j] + 1 > f[i]) {  //从以前的取值中选出最大的
                    f[i] = f[j] + 1;
                }
            }
            if (f[i] == 0) {  //比别人都小或者是第一个元素
                f[i] = 1;
            }
            if (f[i] > max) {
                max = f[i];
            }
        }
        return max;
    }