300. 最長上升子序列

1.想法

最開始我想用回溯法做,但是發(fā)現(xiàn)整個算法的時間復(fù)雜度非常大

• 1.回溯法:

  
  
  image.png
  
  

  每一層的選擇都不影響上一層的選擇,遍歷所有情況最終得到所有的結(jié)果,找出一直遞增的結(jié)果

  
  
  image.png
  
  以題目為例:

1. 如果選擇了10,那么接下來到9就判斷是否能選,因為9<10所以不能選,只能再看下一個,直到101,大于10,所以可以選擇,那么選擇101,計數(shù)+1,并且最大的數(shù)更換成101
2. 如果不選擇10,那么9就可以選擇,選擇9的情況下,暫時最大數(shù)是9,那么同樣的道理到101發(fā)現(xiàn)可以更新
3. 重復(fù)以上過程,直到選擇的次數(shù)達到數(shù)組長度,遞歸結(jié)束

總結(jié):由于每個數(shù)都有兩次的選擇機會,所以時間復(fù)雜度為O(2^n).不滿足條件,所以必須要降低時間復(fù)雜度:降低時間復(fù)雜度的方法,以空間換時間 能以空間換時間的1.直接的容器存儲 不涉及遞歸或者迭代的過程 2.涉及遞歸或者迭代的過程 很明顯貪心法無法直接完成這個過程,那么利用動態(tài)規(guī)劃

2.動態(tài)規(guī)劃

image.png

那么按照動態(tài)規(guī)劃的一般過程進行處理就可以了

1.建模

①解:<max>代表了最長的那么解
②目標函數(shù):max = max(f(0),f(1),...f(n-1))

③約束條件:nums[n]>nums[j] 其中j<n;

2.子問題優(yōu)化

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.歸結(jié)公式

就是說:找出前面所有數(shù)字比現(xiàn)數(shù)字小且其增長序列是最長的

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.動態(tài)規(guī)劃:

    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;
    }