動态規劃算法通常用于求解具有某種最優性質的問題。
那它和貪心有差別嗎？
當然有。不然叫動态規劃幹啥？
幼稚園英語老師：DP是啥？
小盆友：Dog&Peppa pig
英語老斯：恩恩！真聰明！
然而，你是小盆友嗎？
如果是
DP是D****** P*******的縮寫。
意思是動态規劃。
聰明的bolt告訴你：是Dynamic Programming的縮寫！！！
動态規劃注重 表示狀态，轉移狀态
so
講一個栗子：
LIS：
最長上升子序列
這是線性動态規劃中最經典的栗子之一。
最長上升子序列（Longest Increasing Subsequence，LIS），指一個序列中最長的單調遞增的子序列。
注意不是子串，是以可以不相鄰。
比如說：
序列：3 2 1 4 6 8 7 9
它的LIS是5
3 4 6 8 9
或3 4 6 7 9
或2 4 6 8 9
······
還有很多種情況。
于是我們珂以得出：
動态規劃的最優解，有不同的組合情況，但答案隻有一個。
是以，如果NOIP出了動态規劃的題目時，一般會叫你求值，而不是求情況。
這是好處！
BUT，有的老師不會好心，會給更多限制條件，使Ans隻有一種情況，那就更有難度了。
LIS問題要用動态規劃做。
方法一：
這是一個好了解的方法。
但是更好使耗時
不難看出，dp [ i ]就是第 i 個數的LIS
那代碼怎麼實作的呢？
先别急，我們在舉個生活中的栗子。
老師要你算1+2+3+4+5+6+7+8+9=？時，你會算得45，
老師再問你1+2+3+4+5+6+7+8+9+10=？時，你是會用1+···+10，還是用之前算的45+10？
聰明人會用後面一種。
是以，我們根據這個友善的原理，發現我每次計算dp [ i ] 時，如果用到了前面的 dp 值，則會減少一定的計算量。
在我們每次枚舉一個數的dp值時，隻要掃描在它前面比它小的數，那些比他小的數的dp值的最大值+1就是所求數的dp值
因為比所求數小的數的dp值表示它的LIS，再來一個比它大的數，大樹數的LIS就等于小數的LIS+1.
但由于小數的LIS有大有小，我們又要求最長子序列，我們就要取最大值。
一番思考後，我們找到了狀态轉移方程，也就是動态規劃中最重要的東西：
對于每一個 i ，我們枚舉它前面的數 j，if (i > 它前面的數 j ) dp [ i ] = max ( dp [ i ] , dp [ j ] + 1 ) ;
這個算法的時間複雜度是O(n^2)的，慎用。
code:
1 int n,a[1001]/*用來存序列*/,dp[1001]/*dp值*/;//數組大小根據題目而定。
2 cin>>n;
3 dp[1]=1; //1的dp值為1
4 for(int i=1;i<=n;i++)
5 cin>>a[i];
6 for(int i=1;i<=n;i++)
7 {
8 for(int j=1;j<i;j++)
9 {
10 if(a[i]>a[j])
11 {
12 dp[i]=max(dp[i],dp[j]+1); //狀态轉移
13 }
14 }
15 }
16 cout<<dp[n]<<endl; 注意要初始化dp [ 1 ] = 1.剩下的為 0.
還有另一種時間複雜度為 n log n 的LIS算法
看，栗子！
2 1 5 3 6 4 6 3
在 dp 值相同的情況下，保留較小的數顯然更好。因為後面的數若能跟較大的數構成上升子序列，也一定能能較小的數構成上升子序列，反之則不一定。例如 a_3=5 與 a_4=3 的 dp 均為 2，但 a_6=4 不能與 a_3=5 構成上升子序列，而可以和 a_4=3 構成上升子序列。 是以，不同的 dp 值隻需要存一個對應的最小值，将這個最小值順序排列，他們一定是升序（嚴格來說是不下降）的。 于是，借助二分查找的方式，就可以很快查到更新的值，整體時間複雜度 O(nlogn)。
這個就是上面的一個優化，也沒有太多可講的，自己打一遍代碼也就熟了。
code：
1 const int maxn=1e5+5;
2 int a[maxn];
3 int n;
4 int dp[maxn];
5 int ans=1;
6 int find(int x){
7 int l=1,r=ans,m;
8 while(l<r){
9 m=l+(r-l)/2;
10 if(dp[m]>=a[x]){
11 r=m;
12 }
13 else{
14 l=m+1;
15 }
16 }
17 return l;
18 }//二分查找
19 int main(){
20 scanf("%d",&n);
21 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
22 dp[1]=a[1];
23 for(int i=2;i<=n;i++){
24 if(a[i]>dp[ans]){
25 dp[++ans]=a[i];
26 }
27 else{
28 int pos=find(i);
29 dp[pos]=a[i];
30 }
31 }
32 printf("%d",ans);
33 return 0;
34 } 這就是LIS問題，希望大家好好了解這個問題，因為他真的狠重要！
今天的分享就到這裡，我們下次見。