国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

動(dòng)態(tài)規(guī)劃——線性DP

2年前作者：擎天柱的美甲師分類：Toy博客閱讀(26)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了動(dòng)態(tài)規(guī)劃——線性DP。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

動(dòng)態(tài)規(guī)劃——線性DP

最長(zhǎng)不下降序列(LIS)

暴力搜索：由可行的所有起點(diǎn)出發(fā)，搜索出所有的路徑。

動(dòng)態(tài)規(guī)劃——線性DP,算法學(xué)習(xí),動(dòng)態(tài)規(guī)劃,代理模式,算法,c++,學(xué)習(xí)

但是深搜的算法時(shí)間復(fù)雜度要達(dá)到 $O(2^n)$ （每個(gè)數(shù)都有選或不選的兩個(gè)選擇），指數(shù)級(jí)的時(shí)間復(fù)雜度在本題中（ $n \leq 100$ ）顯然是不能接受的。那么再觀察這個(gè)這棵遞歸樹，可以發(fā)現(xiàn)其中有很多重復(fù)的地方。

動(dòng)態(tài)規(guī)劃——線性DP,算法學(xué)習(xí),動(dòng)態(tài)規(guī)劃,代理模式,算法,c++,學(xué)習(xí)

那么如何優(yōu)化呢？

首先可以使用數(shù)組將重復(fù)的部分記錄下來，此后遇到相同的狀態(tài)直接引用已經(jīng)記錄在數(shù)組中的數(shù)據(jù)即可，這樣的方法叫做記憶化搜索，也叫剪枝（后面我們?cè)偌?xì)講）。

所以，如果按照上面的思路將需要計(jì)算的部分用數(shù)組記錄，那么就可以省略那些重復(fù)的部分，所以最終我們需要計(jì)算的就只剩下以從 $1$ 到 $n$ 的每個(gè)點(diǎn)為起點(diǎn)的最長(zhǎng)不下降序列。

以序列 $1, 5, 2, 4, 3$ 為例：

首先將以每個(gè)點(diǎn)為起點(diǎn)的所有長(zhǎng)度都初始化為 $1$ ，所有下一步都初始化為 $0$ 。

起點(diǎn)下標(biāo)	起點(diǎn)數(shù)值	最長(zhǎng)不下降序列的長(zhǎng)度	最長(zhǎng)不下降序列的起點(diǎn)的下一步的下標(biāo)
$5$	$3$	$l e n (3) = 1$	$0$
$4$	$4$	$l e n (4) = 1$	$0$
$3$	$2$	$l e n (2) = ma x (l e n (4), l e n (3)) + 1 = 2$	$4/5$
$2$	$5$	$l e n (5) = 1$	$0$
$1$	$1$	$l e n (1) = ma x (l e n (5), l e n (2), l e n (4), l e n (3)) + 1 = 3$	$3$

綜上，算法分析：

根據(jù)動(dòng)態(tài)規(guī)劃的原理，由后往前進(jìn)行搜索(當(dāng)然從前往后也一樣)。

對(duì) $b (n)$ 來說，由于它是最后一個(gè)數(shù)，所以當(dāng)從 $b (n)$ 開始查找時(shí)，只存在長(zhǎng)度為 $1$ 的不下降序列；
若從 $b (n ? 1)$ 開始查找，則存在下面的兩種可能性：

①若 $b (n ? 1) < b (n)$ ，則存在長(zhǎng)度為 $2$ 的不下降序列 $b (n ? 1)$ ， $b (n)$ 。

②若 $b (n ? 1) > b (n)$ ，則存在長(zhǎng)度為 $1$ 的不下降序列 $b (n ? 1)$ 或 $b (n)$ 。
一般若從 $b (i)$ 開始，此時(shí)最長(zhǎng)不下降序列應(yīng)該按下列方法求出：

在 $b (i + 1), b (i + 2), \dots, b (n)$ 中，找出一個(gè)比 $b (i)$ 大的且最長(zhǎng)的不下降序列，作為它的后繼。

數(shù)據(jù)結(jié)構(gòu)：

為算法上的需要，定義一個(gè)整數(shù)類型二維數(shù)組 $b (N, 3)$

$b (i, 1)$ 表示第 $i$ 個(gè)數(shù)的數(shù)值本身；
$b (i, 2)$ 表示從 $i$ 位置到達(dá) $N$ 的最長(zhǎng)不下降序列長(zhǎng)度；
$b (i, 3)$ 表示從 $i$ 位置開始最長(zhǎng)不下降序列的下一個(gè)位置，若 $b [i, 3] = 0$ 則表示后面沒有連接項(xiàng)。

#include <iostream>
using namespace std;
int b[107][7];
int main()
{
    int n=0;
    while(cin>>b[++n][1]) //b[i][1]表示第i個(gè)數(shù)本身
    {
        b[n][2]=1; //b[i][2]表示以第i個(gè)數(shù)為起點(diǎn)的最長(zhǎng)不下降序列的長(zhǎng)度
        b[n][3]=0; //b[i][3]表示以第i個(gè)數(shù)為起點(diǎn)的最長(zhǎng)不下降序列的起點(diǎn)下一步
    }
    int start=0;
    for(int i=n-1; i; --i)
    {
        int len=0, next=0; //用來記錄以當(dāng)前第i個(gè)點(diǎn)為起點(diǎn)的最長(zhǎng)不下降序列的長(zhǎng)度和下一步的下標(biāo)
        for(int j=i+1; j<=n; ++j)
            if(b[i][1]<b[j][1] && b[j][2]>len) //滿足這樣的兩個(gè)條件才能
                len=b[j][2], next=j;
        if(len) b[i][2]=len+1, b[i][3]=next;
        if(b[i][2]>b[start][2]) start=i; //找到長(zhǎng)度最大的不下降序列，并記錄當(dāng)前序列的起點(diǎn)
    }
    cout<<b[start][2]<<endl;
    while(start)
    {
        cout<<b[start][1]<<" ";
        start=b[start][3];
    }
    return 0;
}

最長(zhǎng)上升序列(LIS)模板：

簡(jiǎn)化題意：求一個(gè)序列的不下降序列的最大長(zhǎng)度。

代碼 $1$ （枚舉起點(diǎn)）

//枚舉起點(diǎn)（從后往前枚舉）
#include <iostream>
using namespace std;
const int N=1e3+7;
int a[N], f[N]; //f[i]表示以第i個(gè)數(shù)為起點(diǎn)的最長(zhǎng)不下降序列的長(zhǎng)度
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
        cin>>a[i], f[i]=1; //將所有值初始化為1
    int ans=1;
    for(int i=n-1; i; --i) //從后往前枚舉
    {
        for(int j=i+1; j<=n; ++j)
            if(a[i]<a[j] && f[j]+1>f[i])
                f[i]=f[j]+1;
        ans=max(ans, f[i]);
    }
    cout<<ans;
    return 0;
}

代碼 $2$ （枚舉終點(diǎn)）

//枚舉終點(diǎn)（從前往后枚舉）
#include <iostream>
using namespace std;
const int N=1e3+7;
int a[N], f[N]; //f[i]表示以第i個(gè)數(shù)為終點(diǎn)的最長(zhǎng)不下降序列的長(zhǎng)度
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
        cin>>a[i], f[i]=1;
    int ans=1;
    for(int i=2; i<=n; ++i) //從前往后枚舉
    {
        for(int j=1; j<i; ++j)
            if(a[j]<a[i] && f[j]+1>f[i])
                f[i]=f[j]+1;
        ans=max(ans, f[i]);
    }
    cout<<ans;
    return 0;
}

模板優(yōu)化

上述代碼的時(shí)間復(fù)雜度為 $O(n^2)$ ，所以如果把數(shù)據(jù)范圍改為 $n \leq 100000$ 也會(huì)出現(xiàn)超時(shí)的情況，所以在這里對(duì)于求最長(zhǎng)不下降序列長(zhǎng)度的問題還可以進(jìn)一步優(yōu)化。在這里對(duì)上述代碼 $2$ 的思路進(jìn)一步思考。（優(yōu)化的過程其實(shí)就是一個(gè)去除冗余的過程。）

用以下樣例作為引子：

Input:
7
3 1 2 1 8 5 6
Output:
4

枚舉每一個(gè)點(diǎn)作為終點(diǎn)，從第一個(gè)數(shù) $3$ 開始， $3$ 可以作為一個(gè)長(zhǎng)度為 $1$ 的最長(zhǎng)不下降序列，接著到第二個(gè)數(shù) $1$ ，也是一個(gè)長(zhǎng)度為 $1$ 的長(zhǎng)度為 $1$ 的最長(zhǎng)不下降序列……，對(duì)于后面的每個(gè)數(shù)，如果它可以接到 $3$ 的后面，那么它一定可以接到 $1$ 的后面，所以以 $3$ 為結(jié)尾長(zhǎng)度為 $1$ 的最長(zhǎng)不下降序列就沒有必要存下來了，因?yàn)? $1$ 比 $3$ 更優(yōu)（后面可以接的數(shù)范圍更廣，即更小的數(shù)值作為結(jié)尾更優(yōu)）。所以我們也沒有必要將所有長(zhǎng)度為 $1$ 的序列都存下來，只需要每次存下那個(gè)相同長(zhǎng)度下最優(yōu)的情況的結(jié)尾數(shù)值即可。

那么對(duì)于當(dāng)前的不下降子序列的長(zhǎng)度 $i$ ，一定有一個(gè)結(jié)尾值 $f [i]$ ，則有

結(jié)論：對(duì)于不同長(zhǎng)度的序列的結(jié)尾數(shù)值一定是隨著序列長(zhǎng)度的增加而嚴(yán)格單調(diào)遞增的。

證明（反證法）：

假設(shè)存在長(zhǎng)度為 $i$ 的序列結(jié)尾數(shù)值 $f [i]$ 小于或等于長(zhǎng)度為 $i ? 1$ 的序列結(jié)尾數(shù)值 $f [i ? 1]$ ，即 $f [i] \leq f [i ? 1]$ 。

由于每個(gè)序列都是一個(gè)不下降序列，所以當(dāng)前長(zhǎng)度為 $i$ 的序列的倒數(shù)第二個(gè)數(shù) $x$ 一定滿足關(guān)系： $x \leq f [i] \leq f [i ? 1]$ 。但若如此，在前面遍歷的時(shí)候，對(duì)于長(zhǎng)度為 $i ? 1$ 的序列的結(jié)尾更優(yōu)的結(jié)果應(yīng)該選擇的是比當(dāng)前 $f [i ? 1]$ 更小的 $x$ ，所以這與我們最終選擇的 $f [i ? 1]$ 相悖。

所以假設(shè)（存在長(zhǎng)度為 $i$ 的序列結(jié)尾數(shù)值 $f [i]$ 小于或等于長(zhǎng)度為 $i ? 1$ 的序列結(jié)尾數(shù)值 $f [i ? 1]$ ，即 $f [i] \leq f [i ? 1]$ ）不成立。

所以對(duì)于不同長(zhǎng)度的序列的結(jié)尾數(shù)值一定是隨著序列長(zhǎng)度的增加而嚴(yán)格單調(diào)遞增的結(jié)論成立。

動(dòng)態(tài)規(guī)劃——線性DP,算法學(xué)習(xí),動(dòng)態(tài)規(guī)劃,代理模式,算法,c++,學(xué)習(xí)

有了這樣的前提，如果想求以 $a [i]$ 結(jié)尾的最長(zhǎng)不下降子序列的長(zhǎng)度應(yīng)該如何解決呢？

屆時(shí)，只需要找到一個(gè)最大的比 $a [i]$ 小的數(shù) $f [j]$ ，并將 $a [i]$ 接到其后面即可，這樣所得到的以 $a [i]$ 為結(jié)尾的最長(zhǎng)不下降子序列的長(zhǎng)度就是 $j + 1$ 。這時(shí)還需要更新一下， $f [j + 1]$ ，因?yàn)殚L(zhǎng)度為 $j + 1$ 的序列的結(jié)尾 $a [i]$ 一定是小于先前的長(zhǎng)度為 $j + 1$ 的序列的結(jié)尾數(shù)的。

那么這個(gè)過程中如何找到這個(gè)最大的比 $a [i]$ 小的數(shù)呢？肯定不能選擇逐個(gè)遍歷這樣的方法的，因?yàn)檫@樣的時(shí)間復(fù)雜度就又回到了優(yōu)化前的 $O(n^2)$ 。

這時(shí)就用到前面的結(jié)論了：對(duì)于不同長(zhǎng)度的序列的結(jié)尾數(shù)值一定是隨著序列長(zhǎng)度的增加而嚴(yán)格單調(diào)遞增的結(jié)論成立。既然是嚴(yán)格單調(diào)上升的序列，尋找其中一個(gè)數(shù)，我們就可以想到使用二分法。

簡(jiǎn)單介紹二分法（具體我們后面會(huì)在學(xué)習(xí)分治思想的時(shí)候繼續(xù)講）：二分查找也稱折半查找，顧名思義，就是每次查找去掉不符合條件的一半?yún)^(qū)間，直到找到答案（整數(shù)二分）或者和答案十分接近（浮點(diǎn)二分）。

#include <iostream>
using namespace std;
const int N=1e5+7;
int a[N], f[N]; //f[i]表示長(zhǎng)度為i的最長(zhǎng)不下降子序列的最后一個(gè)值
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];
    int len=0;
    f[1]=-2e9;
    for(int i=1; i<=n; ++i)
    {
        int l=0, r=len;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(f[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len, r+1);
        f[r+1]=a[i];
    }
    cout<<len;
    return 0;
}

最長(zhǎng)公共子序列(LCS)

狀態(tài)表示：

設(shè) $f [i] [j]$ 表示 $s 1$ 的前 $i$ 個(gè)字符與 $s 2$ 的前 $j$ 個(gè)字符的最大公共子序列的長(zhǎng)度了

設(shè)字符串 $s 1$ 和 $s 2$ 的長(zhǎng)度分別為 $l e n 1$ 和 $l e n 2$ ，則 $s 1$ 和 $s 2$ 的最大公共子序列的長(zhǎng)度為 $f [l e n 1] [l e n 2]$

狀態(tài)初始化：

$f [l e n 1] [0] = 0$ ， $f [0] [l e n 2] = 0$

狀態(tài)轉(zhuǎn)移：（分為三種情況討論）

$s 1 [i]$ 不在公共子序列中：該情況下 $f [i] [j] = f [i ? 1] [j]$

$s 2 [j]$ 不在公共子序列中：該情況下 $f [i] [j] = f [i] [j ? 1]$

$s 1 [i]$ 和 $s 2 [j]$ 都在公共子序列中（且 $s 1 [i] = s 2 [j]$ ）：該情況下 $f [i] [j] ? f [i ? 1] [j ? 1] + 1$

$f [i] [j]$ 取上述三種情況的最大值（第三種情況要求 $s 1 [i] = s 2 [j]$ ）

以 $s 1 = B D C A B A$ 和 $s 2 = A BCB D A B$ 兩個(gè)字符串為例：

			A	B	C	B	D	A	B
	$s 1$ \ $s 2$	〇	①	②	③	④	⑤	⑥	⑦
	〇	0	0	0	0	0	0	0	0
B	①	0	0	1	1	1	1	1	1
D	②	0	0	1	1	1	2	2	2
C	③	0	0	1	2	2	2	2	2
A	④	0	1	1	2	2	2	3	3
B	⑤	0	1	2	2	3	3	3	4
A	⑥	0	1	2	2	3	3	4	4

代碼

#include <iostream>
#include <cstring>
using namespace std;
const int N=207;
char s1[N], s2[N];
int f[N][N];
int main()
{
	scanf("%s%s", s1+1, s2+1); //注意將下標(biāo)為0的位置空出來，避免后面的狀態(tài)
	for(int i=1; s1[i]; ++i)
		for(int j=1; s2[j]; ++j)
			if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1;
			else f[i][j]=max(f[i][j-1], f[i-1][j]);
	int len1=strlen(s1+1), len2=strlen(s2+1);
	cout<<f[len1][len2];
	return 0;
}

最長(zhǎng)公共上升子序列(LCIS)

動(dòng)態(tài)規(guī)劃——線性DP,算法學(xué)習(xí),動(dòng)態(tài)規(guī)劃,代理模式,算法,c++,學(xué)習(xí)

樸素

首先按照上述思路用代碼實(shí)現(xiàn)出來：

#include <iostream>
using namespace std;
const int N=3e3+7;
int a[N], b[N], f[N][N];
//f[i][j]表示所有在a[1~i]和b[1~j]中都出現(xiàn)過
//且以b[j]結(jié)尾的公共上升子序列的集合
int main()
{
	int n;
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=1; i<=n; ++i) cin>>b[i];
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=n; ++j)
		{
			f[i][j]=f[i-1][j]; //a[i]!=b[j]（以b[j]結(jié)尾且不包含a[i]）
			if(a[i]==b[j])
			{
				int mx=0;
				for(int k=1; k<j; ++k) //遍歷找出b[j]前一個(gè)是由哪個(gè)狀態(tài)轉(zhuǎn)移過來的
					if(b[k]<b[j]) //滿足“上升”條件
						mx=max(f[i-1][k]+1, mx); //加上的1就是當(dāng)前的b[j]
				f[i][j]=max(f[i][j], mx);
			}
		}
	int ans=0;
	for(int i=1; i<=n; ++i)
		ans=max(f[n][i], ans);
	cout<<ans;
	return 0;
}

優(yōu)化

上述代碼一個(gè)明顯的弊端在于它的三層循環(huán)，時(shí)間復(fù)雜度達(dá)到了 $O(n^3)$ 。那么如何優(yōu)化呢？顯然可以從最內(nèi)層的循環(huán)下手。

for(int k=1; k<j; ++k)
	if(b[k]<b[j])
		mx=max(f[i-1][k]+1, mx);

這里有一個(gè)小細(xì)節(jié)的處理：當(dāng)前循環(huán)是在 $a [i] == b [j]$ 的條件下的，所以循環(huán)中的判斷條件 $b [k] < b [j]$ 也可以改成 $b [k] < a [i]$ ，即：

for(int k=1; k<j; ++k)
	if(b[k]<a[i])
		mx=max(f[i-1][k]+1, mx);

思考：該循環(huán)的目的是什么呢？

每個(gè) $b [k]$ 都對(duì)應(yīng)一個(gè)狀態(tài) $f [i ? 1, k]$ 。那么當(dāng)前循環(huán)相當(dāng)于是在 $b [1], b [2], b [3], ..., b [j ? 1]$ 中找出所有小于 $a [i]$ 的數(shù)，并在比較他們分別對(duì)應(yīng)的 $f [i ? 1, k]$ 之后選出一個(gè)最大值，作為當(dāng)前狀態(tài)的上一個(gè)狀態(tài)。這些狀態(tài)的大小都是固定不變的，所以在當(dāng)前一輪中我們比較了 $f [i ? 1, 1], f [i ? 1, 2], f [i ? 1, 3], ..., f [i ? 1, j ? 1]$ 之后，在下一輪比較 $f [i ? 1, 1], f [i ? 1, 2], f [i ? 1, 3], ..., f [i ? 1, j ? 1], f [i ? 1] [j]$ 的時(shí)候又將前面的這些拿過來重復(fù)對(duì)比了一次，所以這里多了很多重復(fù)的部分。那么想要將這層循環(huán)優(yōu)化掉，則可以直接比較當(dāng)前 $b [j]$ 和 $a [i]$ 即可：只有 $a [i] = b [j]$ 的時(shí)候才更新當(dāng)前的 $f [i] [j]$ ，只有當(dāng) $b [j] < a [i]$ 的時(shí)候我們才要去更新前綴的最大值。

如圖示：當(dāng)前被?的所有數(shù)，在之后比較中還會(huì)被再拿出來進(jìn)行比較。

動(dòng)態(tài)規(guī)劃——線性DP,算法學(xué)習(xí),動(dòng)態(tài)規(guī)劃,代理模式,算法,c++,學(xué)習(xí)

#include <iostream>
using namespace std;
const int N=3e3+7;
int a[N], b[N], f[N][N];
int main()
{
	int n;
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=1; i<=n; ++i) cin>>b[i];
	for(int i=1; i<=n; ++i)
	{
		int mx=1;
		for(int j=1; j<=n; ++j)
		{
			f[i][j]=f[i-1][j];
			if(a[i]==b[j]) f[i][j]=max(mx, f[i][j]); //更新f[i][j]這個(gè)狀態(tài)值
			else if(b[j]<a[i]) mx=max(mx, f[i-1][j]+1); //更新前綴的最大值
		}
	}
	int ans=0;
	for(int i=1; i<=n; ++i)
		ans=max(f[n][i], ans);
	cout<<ans;
	return 0;
}

再優(yōu)化

將狀態(tài)數(shù)組由二維壓縮成一維：

#include <iostream>
using namespace std;
const int N=3e3+7;
int a[N], b[N], f[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=1; i<=n; ++i) cin>>b[i];
	for(int i=1; i<=n; ++i)
	{
		int mx=1;
		for(int j=1; j<=n; ++j)
			if(a[i]==b[j])
				f[j]=max(mx, f[j]);
			else if(b[j]<a[i])
				mx=max(mx, f[j]+1);
	}
	int ans=0;
	for(int i=1; i<=n; ++i)
		ans=max(f[i], ans);
	cout<<ans;
	return 0;
}

攔截導(dǎo)彈(missile)

該問題的第一問是要求一個(gè)最長(zhǎng)不上升序列的長(zhǎng)度，典型的LIS問題。

第二問用貪心的思路做：

貪心流程：從前往后掃描每個(gè)數(shù)，對(duì)于每個(gè)數(shù)：

情況 $1$ ：如果現(xiàn)有的子序列的結(jié)尾都小于當(dāng)前數(shù)，則創(chuàng)建新的子序列
情況 $2$ ：將當(dāng)前數(shù)放到結(jié)尾大于等于它的最小子序列后面

設(shè) $A$ 為貪心算法得到的序列個(gè)數(shù)； $B$ 表示最優(yōu)解；如果能證明 $A \geq B$ 并且 $A \leq B$ ，那么就可以得到 $A = B$ 。

因?yàn)樽顑?yōu)解一定是最少的答案，所以貪心算法的結(jié)果一定大于等于最優(yōu)解，即 $A \geq B$ ；

那么接下來如何證明 $A \leq B$ 呢？可以使用調(diào)整法：假設(shè)最優(yōu)解對(duì)應(yīng)的方案數(shù)與貪心算法算出當(dāng)前的方案不同。

找到第一個(gè)不同的數(shù)：假設(shè)當(dāng)前貪心算法找到的方案應(yīng)該將當(dāng)前的 $x$ 接到 $a$ 的后面，即 $a$ 是大于等于 $x$ 的最小子序列的結(jié)尾；而最優(yōu)解這個(gè)時(shí)候是將 $x$ 接到 $b$ 的后面，由于 $a$ 是大于等于 $x$ 的最小數(shù)，所以一定有 $b \geq a$ ，那接下來兩種結(jié)果引出來的序列，是可以進(jìn)行交換的（因?yàn)? $x \leq a \leq b$ ，所以 $x$ 可以接在 $a$ 后面，也可以接在 $b$ 后面），調(diào)換后的結(jié)果并不影響最終的序列個(gè)數(shù)。
動(dòng)態(tài)規(guī)劃——線性DP,算法學(xué)習(xí),動(dòng)態(tài)規(guī)劃,代理模式,算法,c++,學(xué)習(xí)

所以當(dāng)前方案即使不同，貪心算法最終算出來的方案數(shù)也是與最優(yōu)解的方案數(shù)是相同的。所以當(dāng)前貪心算法就是最優(yōu)算法。

代碼 $1$

#include <iostream>
using namespace std;
const int N=1e3+7;
int n, a[N], f[N], g[N];
int main()
{
    while(cin>>a[++n]);
    int res=0;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<i; ++j)
            if(a[j]>=a[i])
                f[i]=max(f[i], f[j]+1);
        res=max(res, f[i]);
    }
    cout<<res<<endl;
    int cnt=0;
    for(int i=1; i<=n; ++i)
    {
        int k=0;
        while(k<cnt && g[k]<a[i]) k++;
        g[k]=a[i];
        if(k>=cnt) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

對(duì)于一個(gè)序列，最少用到的可將其覆蓋的非上升子序列的個(gè)數(shù)與最大上升子序列的長(zhǎng)度是相同的，這兩個(gè)問題是一個(gè)對(duì)偶問題（離散數(shù)學(xué)中的反鏈定理Dilworth定理）。

所采用的做法完全相同 $=>$ 最終求得的結(jié)果完全相同 $=>$ 解決的問題完全相同

代碼 $2$ 文章來源地址http://www.zghlxwxcb.cn/news/detail-803157.html

#include <iostream>
using namespace std;
const int N=1e3+7;
int a[N], f1[N], f2[N];
int main()
{
    int n=0, ans1=0, ans2=0;
    while(scanf("%d", &a[++n])!=EOF) f2[n]=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            if(a[j]>=a[i]) f1[i]=max(f1[i], f1[j]+1);
            else f2[i]=max(f2[i], f2[j]+1);
        }
        ans1=max(ans1, f1[i]);
        ans2=max(ans2, f2[i]);
    }
    printf("%d\n%d", ans1, ans2);
    return 0;
}

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——線性DP的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

猿創(chuàng)征文 |【算法面試入門必刷】動(dòng)態(tài)規(guī)劃-線性dp（一）
??個(gè)人主頁：一二三o-0-O的博客 ??技術(shù)方向：C/C++客戶端資深工程師（直播+音視頻剪輯） ?????作者簡(jiǎn)介：數(shù)據(jù)結(jié)構(gòu)算法與音視頻領(lǐng)域創(chuàng)作者 ?? 系列專欄：?？途W(wǎng)面試必刷 ??專欄目標(biāo)：幫助伙伴們通過系統(tǒng)訓(xùn)練，掌握數(shù)據(jù)結(jié)構(gòu)與算法，收獲心儀Offer ??推薦一個(gè)找工作
2024年02月03日
瀏覽(31)
動(dòng)態(tài)規(guī)劃(DP)入門——線性DP
在了解線性DP之前，我們首先要知道什么是動(dòng)態(tài)規(guī)劃，即為將一種復(fù)雜問題，分解成很多重疊的子問題，并通過子問題的解得到整個(gè)問題的解的算法。聽起來比較抽象，動(dòng)態(tài)規(guī)劃簡(jiǎn)單來說就是確定問題的狀態(tài)，通常題目都會(huì)提示，一般為“到第i個(gè)為止，xx為j(xx為k)的方案數(shù)/最
2024年02月19日
瀏覽(25)
動(dòng)態(tài)規(guī)劃——線性DP
暴力搜索：由可行的所有起點(diǎn)出發(fā)，搜索出所有的路徑。但是深搜的算法時(shí)間復(fù)雜度要達(dá)到 O ( 2 n ) O(2^n) O ( 2 n ) （每個(gè)數(shù)都有選或不選的兩個(gè)選擇），指數(shù)級(jí)的時(shí)間復(fù)雜度在本題中（ n ≤ 100 n≤100 n ≤ 100 ）顯然是不能接受的。那么再觀察這個(gè)這棵遞歸樹，可以發(fā)現(xiàn)其中有很
2024年01月19日
瀏覽(26)
動(dòng)態(tài)規(guī)劃：線性DP
2024年02月06日
瀏覽(24)
動(dòng)態(tài)規(guī)劃算法學(xué)習(xí)一：DP的重要知識(shí)點(diǎn)、矩陣連乘算法
三部曲如下三步：基本原則：“空間換時(shí)間” 存儲(chǔ)重復(fù)子問題的解，減少運(yùn)算時(shí)間底層運(yùn)算：“表格操作” 用表格存儲(chǔ)子問題的解實(shí)現(xiàn)路線：“子問題劃分、自底向上求解” 利用表格中存儲(chǔ)的子問題的解，求上一層子問題的解。矩陣連乘計(jì)算次序可以用加括號(hào)的方式
2024年02月09日
瀏覽(24)
[動(dòng)態(tài)規(guī)劃]——線性DP(LIS/LCS/LCIS等) 詳解
線性DP，是較常見的一類動(dòng)態(tài)規(guī)劃問題，其是在線性結(jié)構(gòu)上進(jìn)行狀態(tài)轉(zhuǎn)移，這類問題不像背包問題、區(qū)間DP等有固定的模板線性動(dòng)態(tài)規(guī)劃的目標(biāo)函數(shù)為特定變量的線性函數(shù)，約束是這些變量的線性不等式或等式，目的是求目標(biāo)函數(shù)的最大值或最小值因此，除了少量問題（如：
2024年02月10日
瀏覽(18)
DP算法：動(dòng)態(tài)規(guī)劃算法
（1）確定初始狀態(tài) （2）確定轉(zhuǎn)移矩陣，得到每個(gè)階段的狀態(tài)，由上一階段推到出來（3）確定邊界條件。藍(lán)橋杯——印章（python實(shí)現(xiàn)）使用dp記錄狀態(tài)，dp[i][j]表示買i張印章，湊齊j種印章的概率 i表示買的印章數(shù)，j表示湊齊的印章種數(shù) 情況一：如果ij,不可能湊齊印章，概
2024年02月07日
瀏覽(21)
【LeetCode: 2369. 檢查數(shù)組是否存在有效劃分 | 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃 | 線性dp】
?? 算法題 ?? ?? 算法刷題專欄 | 面試必備算法 | 面試高頻算法 ?? ?? 越難的東西,越要努力堅(jiān)持，因?yàn)樗哂泻芨叩膬r(jià)值，算法就是這樣? ?? 作者簡(jiǎn)介：碩風(fēng)和煒，CSDN-Java領(lǐng)域新星創(chuàng)作者??，保研|國家獎(jiǎng)學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文
2023年04月19日
瀏覽(36)
動(dòng)態(tài)規(guī)劃（DP）（算法筆記）
本文內(nèi)容基于《算法筆記》和官方配套練題網(wǎng)站“晴問算法”，是我作為小白的學(xué)習(xí)記錄，如有錯(cuò)誤還請(qǐng)?bào)w諒，可以留下您的寶貴意見，不勝感激。動(dòng)態(tài)規(guī)劃(Dynamic Programming,DP)是一種用來解決一類最優(yōu)化問題的算法思想。簡(jiǎn)單來說，動(dòng)態(tài)規(guī)劃將一個(gè)復(fù)雜的問題分解成若干個(gè)子
2024年02月05日
瀏覽(20)
★動(dòng)態(tài)規(guī)劃（DP算法）詳解
什么是動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃_百度百科內(nèi)容太多了不作介紹，重點(diǎn)部分是無后效性，重疊子問題，最優(yōu)子結(jié)構(gòu)。問S-P1和S-P2有多少種路徑數(shù)，毫無疑問可以先從S開始深搜兩次，S-P1和S-P2找出所有路徑數(shù)，但是當(dāng)這個(gè)圖足夠大，那就會(huì)超時(shí)。動(dòng)態(tài)規(guī)劃旨在用空間換時(shí)間，我們
2024年02月04日
瀏覽(23)

<li id="sfj16"><small id="sfj16"></small></li>

<ul id="sfj16"><sup id="sfj16"></sup></ul>

<b id="sfj16"></b>