動态規劃入門 & 線性動态規劃

參考文獻：全國青少年資訊學競賽教育訓練教材——複賽（陳合力 遊光輝 編著）

一、概念

在多階段決策的問題中，各階段采取的決策，一般倆說是與空間或者時間相關的。決策依賴于目前狀态，又随即引起狀态的轉移，一個決策序列就是在變化的狀态中産生出來，故有動态的含義。

我們稱這種解決多階段決策最優化的過程稱為動态規劃方法。

例如在一個m*n的迷宮中，從左下角走到右上角

可以看到，狀态A和狀态B應當屬于同一個階段。T可以從A走來，也可以從B走來，故dp[T]=min(dp[A]+map[A][T],dp[B]+map[B][T]);即終點的最短路應當是A或者B的最短路+最後一段長度.

動态規劃的幾個術語：

階段：把所求問題的過程按照時間或者空間恰當地劃分成若幹個互相聯系的階段。

狀态：表示每個階段的客觀狀态，它既是每個階段的出發位置，又是前一階段的終點。

無後效性：如果給定某一階段的狀态，則在這一階段以後的過程發展不受這個階段以前的各個狀态的影響，是以各階段确定了，整個過程也就确定了。

決策：一個階段的狀态給定之後，從該狀态演變到下一狀态的一種選擇。

政策：每個階段決策組成的序列。

最優性原理：把一個大問題劃分成多個子問題，對于整個問題必須最優的情況時，子問題也必須最優，即問題具備最優子結構的性質。

二、線性動态規劃

線性動态規劃中狀态是一維的，第i個元素的狀态與前i-1個元素的狀态有關，前i-1個狀态組成一個決策序列，它是其他類動态規劃的基礎。

最長不下降子序列

Given an unsorted array of integers, find the length of longest

increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest

increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Note that there may be more than one LIS combination, it is only

necessary for you to return the length.

我們用dp[i]表示序列長度為i的時候最長不下降子序列的長度。

當序列長度為i時，dp[i]=max{d[j]}+1(0<=j

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size(),dp[n];
        memset(dp,,sizeof(dp));
        dp[]=;
        for(int i=;i<n;i++){
            //求取前j個最大并且nums[j]<nums[i]的
            //這裡max需要設定為0，這樣就可以在沒有找到最大值的情況下，也不需要設定額外的找到flag
            //使dp[i]=1
            int max=;
            for(int j=i-;j>=;j--)
            if(nums[j]<nums[i] && dp[j]>max)
            max=dp[j];

            //應用dp方程
            dp[i]=max+;
        }
        int max=;
        for(int i=;i<n;i++)
        if(dp[i]>max) max=dp[i];
        return max;
    }
};
           

合唱隊形

題目描述： N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學不交換位置就能排成合唱隊形。

合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編号為1, 2, …, K，他們的身高分别為T1, T2, …, TK， 則他們的身高滿足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。

你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。

輸入： 輸入的第一行是一個整數N（2 <= N <= 100），表示同學的總數。 第一行有n個整數，用空格分隔，第i個整數Ti（130 <= Ti <= 230）是第i位同學的身高（厘米）。

輸出： 可能包括多組測試資料，對于每組資料，輸出包括一行，這一行隻包含一個整數，就是最少需要幾位同學出列。

樣例輸入：

8

186 186 150 200 160 130 197 220

分别求出從左往右最長遞增序列，從右往左最長遞增序列（即從左往右遞減）。

計算每一個位置作為中點的時候，隊伍能達到的長度，取最長。

注意求從左往右遞減的時候，需要從n-1開始周遊，否則不滿足無後效性的條件

#include<stdio.h> 
#include<string.h>
#include<stdlib.h>
#define N 101
using namespace std;

int increase[N],decrease[N],height[N];

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){

        for(int i=;i<n;i++){
            scanf("%d",&height[i]);
            increase[i]=;
            decrease[i]=;
        }

        //從左往右找遞增
        for(int i=;i<n;i++) {
            for(int j=i-;j>=;j--){
                if(increase[j]+>increase[i] && height[j]<height[i]) 
                increase[i]=increase[j]+;
            }
        }

        //這樣是不科學的
        //不滿足無後效性，即确定了dp[i]之後，仍然有可能出現比它小的值，使d[i]的值增加 
    //  for(int i=0;i<n;i++) {
    //      int max=0;
    //      for(int j=i-1;j>=0;j--){
    //          if(decrease[j]>max && height[j]>height[i])
    //          max=decrease[j];
    //      }
    //      decrease[i]=max+1;
    //  }
        for(int i=n-;i>=;i--) {
            for(int j=i+;j<n;j++){
                if(decrease[j]+>decrease[i] && height[j]<height[i])
                decrease[i]=decrease[j]+;
            }
        }

        int max=;
        for(int i=;i<n;i++){
            if(increase[i]+decrease[i]- > max)
            max=increase[i]+decrease[i]-;
        }

        printf("%d\n",n-max);
    }
//  system("pause");
    return ;
}
           

最長公共子序列

設定dp[i][j]表示下标為0~i和0~j之間的最長公共子序列的長度。

對于這兩個序列，當最後一個元素相等時，将轉化為前a[0~i-1] b[0~j-1]的問題。

否則，其最長長度為dp[i-1][j] dp[i][j-1]的最大值

具備最優子結構性質。

從左往右推導，可以保證在dp[i][j]的情況下，dp[i-1][j] dp[i][j-1]均已求出。

//核心代碼
for(int i=;i<lena;i++){
    for(int j=;j<lenb;j++){
        if(a[i]==b[j])
        dp[i][j]=dp[i-][j-]+;
        else dp[i][j]=max(dp[i][j-],dp[i-][j]);
    }
}
printf("%d\n",dp[lena-][lenb-]);