算法學習記錄：動態(tài)規(guī)劃

這篇具有很好參考價值的文章主要介紹了算法學習記錄：動態(tài)規(guī)劃。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

前言：

背景知識：

正文：

?什么是動態(tài)規(guī)劃（更新中）：

?理解動態(tài)規(guī)劃：

狀態(tài)：

狀態(tài)轉移：

?運用動態(tài)規(guī)劃（分析步驟）：

例題集（時間順序）?

1.藍橋OJ 3820：混境之地5（DFS）

2.藍橋OJ 216：地宮取寶（DFS）

3.藍橋OJ 1536：數(shù)字三角形（迭代法）

4.藍橋OJ 3367：破損的樓梯（迭代法）

5.藍橋OJ 3423：安全序列（迭代法）

6.藍橋OJ 389：擺花（二維DP）（迭代法）

7.藍橋OJ 3362：建造房屋（二維DP）（迭代法）

?8.最長上升子序列（LIS）

藍橋OJ 1358：藍橋勇士

藍橋OJ 742：合唱隊形

9.最長子序列（LCS）

藍橋OJ 1189：最長公共子序列

10.藍橋OJ 3349：可構造的序列總數(shù)（二維DP）

11.藍橋OJ 3349：最快洗車時間（二維DP）

前言：

? 算法學習記錄不是算法介紹，本文記錄的是從零開始的學習過程（見到的例題，代碼的理解……），所有內容按學習順序更新，而且不保證正確，如有錯誤，請幫助指出。

學習工具：藍橋OJ，LeetCode

背景知識：

你已經了解過DFS。

（算法學習記錄：DFS）

正文：

?什么是動態(tài)規(guī)劃（更新中）：

全稱”Dynamic Programing“，是將復雜問題分解成很多重疊的子問題，并通過子問題的解得到整個問題的解的算法。

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

關系：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

?圖中認為（遞歸+記憶化）屬于動態(tài)規(guī)劃，這個不完全正確：

動態(tài)規(guī)劃一個明顯的特征是它涉及求最值：

它與DFS的不同點：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

相同點：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

?理解動態(tài)規(guī)劃：

可以通過用記憶化DFS求解斐波那契問題，來理解動態(tài)規(guī)劃中的狀態(tài)轉移。

DFS + 記憶化的算法學習記錄

狀態(tài)：

形如dp[i][j] = val 的取值，用于描述、確定狀態(tài)所需的變量

狀態(tài)轉移：

狀態(tài)與狀態(tài)的轉移關系，一般可以表示為一個數(shù)學表達式，轉移的方向決定迭代或遞歸的方向。

?運用動態(tài)規(guī)劃（分析步驟）：

1.確定狀態(tài)，題目關鍵詞”到第i個為止、xx為j（xx為k）的方案數(shù)/最小代價/最大價值……“

2.確定狀態(tài)轉移方程，從已知狀態(tài)得到新狀態(tài)的方法

3.根據(jù)狀態(tài)轉移的方向決定使用迭代法還是遞歸法（記憶化）

例題集（時間順序）?

1.藍橋OJ 3820：混境之地5（DFS）

dp[x][y][t]表示從起點到點(x,y)，且噴氣背包使用了t次的?狀態(tài)?下是否可以到終點。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9 + 7;
const int inf = 1e9,N = 1e3 + 3;
 
int n,m,k,sx,sy,fx,fy,h[N][N];
 
 
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
bool inmp(int x,int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
 
//返回值表示能否到達終點(fx,fy),t表示當前使用的噴氣背包的次數(shù)
 
bool dfs(int x,int y,int t)
{
	if(x == fx && y == fy)return true;
	
	for(int i = 0;i < 4 ;i ++)
	{
		int nx = x + dx[i],ny = y + dy[i];
		
		if(!inmp(nx,ny))continue;
		
		if(!t)
		{
			//不用
			if(h[x][y] > h[nx][ny] && dfs(nx,ny,0))return true;
			
			if(h[x][y] + k > h[nx][ny] && dfs(nx,ny,1))return true;
		}else
		{
			if(h[x][y] > h[nx][ny] && dfs(nx,ny,1))return true;
		}
	}
	return false;
}
 
int main()
{
	cin >> n >> m >> k;
	cin >> sx >> sy >> fx >> fy;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++)
		{
			cin >> h[i][j];
		}
	}
	
	cout << (dfs(sx,sy,0)?"Yes" : "No") << '\n';
	return 0;
}

2.藍橋OJ 216：地宮取寶（DFS）

設置狀態(tài)：dp[x][y][mx][cnt]表示走到(x,y)，手中cnt個寶，且最大值為mx的方案

注意：開dp數(shù)組時要估算大小，這個四維數(shù)組占用空間約1e6，已經接近上限。

#include<bits/stdc++.h>
using namespace std;
 
using ll = long long ;
const ll p = 1e9 + 7;
const int inf = 1e9 ,N = 55;
 
int n,m,k,c[N][N];
 
int dx[] = {0,1};
int dy[] = {1,0};
 
 
int dp[N][N][15][15]; 
 
bool inmp(int x,int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
 
ll dfs(int x,int y,int mx, int cnt)
{
	if( x == n && y == m )return (ll)(cnt == k);
	if(dp[x][y][mx][cnt] != -1)return dp[x][y][mx][cnt];
	
	ll res = 0;
	
	for(int i = 0;i < 2;i ++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		
		if(!inmp(nx,ny))continue;
		
		//拿上這個寶貝
		if(c[nx][ny] > mx && cnt < k)res = (res + dfs(nx,ny,c[nx][ny],cnt + 1)) % p;
		
		//不拿這個寶貝
		res = (res + dfs(nx,ny,mx,cnt)) % p;
		
	}
	return dp[x][y][mx][cnt] = res;
}
 
int main()
{
	memset(dp,-1,sizeof dp);
	cin >> n >> m >> k;
	
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++)
		{
			cin >> c[i][j];
			c[i][j] ++;   //整體加1不影響結果，這樣對mx可以設置初值為0，避免數(shù)組越界到-1
		}
	}
	cout << (dfs(1,1,0,0) + dfs(1,1,c[1][1],1)) % p;
	
	return 0;
}

3.藍橋OJ 1536：數(shù)字三角形（迭代法）

方案一（未通過）：

設狀態(tài)dp[i][j]表示從第i行第j列的元素往下走的所有路徑當中最大的和

狀態(tài)轉移方程：dp[ i ][ j ] = max( dp [ i + 1 ][ j ] ,dp[ i + 1 ][ j + 1 ] )

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 105;
ll a[N][N],dp[N][N];

int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n;i ++)
	    for(int j = 1;j <= i; ++ j)cin >> a[i][j];
	
	for(int i = n;i >= 1; --i)
		for(int j = 1;j <= i; ++j){
		dp[i][j] = a[i][j] + max(dp[i + 1][j],dp[i + 1][j + 1]);
	}
	cout << dp[1][1] << endl;
	return 0;
}

?方案二（可行）：

思路一的問題是沒有考慮題中條件：“次數(shù)相差不能超過1”

為了解決這個問題，考慮次數(shù)相差符合要求的解的特征：

1.若最后一行奇數(shù)個元素：只有中間那個作出口才行

2.若最后一行偶數(shù)個元素：中間兩個作出口都有可能

還要考慮取最大值，因此：

設置狀態(tài)A[i][j]表示頂點到該位置路程最大值

狀態(tài)轉移方程：A[ i ][ j ] = A[ i?][ j ]?+ max( A[ i -?1 ][ j - 1?] , A[ i -?1 ][ j ] )

#include<bits/stdc++.h>
using namespace std;
int Max(int a,int b){//返回a，b的最大值 

	return (a>b?a : b);
}
int main() 
{
	int n;
	cin >> n;
	int An[n][n];//儲存三角形每個位置的值 
	
	for(int i = 0; i < n; i ++)//三角形的行i的循環(huán) 
	{
		for(int j = 0; j < i + 1; j ++)//三角形列j的循環(huán)，列最大等于該行的行數(shù) 
		{
			scanf("%d", &An[i][j]);
		}
	}
	for(int i = 0; i < n; i ++)//三角形的行i的循環(huán) 
	{
		for(int j = 0; j < i + 1; j ++)//三角形列j的循環(huán)，列最大等于該行的行數(shù) 
		{
			if(i >= 1)//不是第一列只有一個數(shù)的情況下 
			{
				if(j == 0)//數(shù)組第一列沒有左上角的值，直接加上面的值就是最大值 
					An[i][j] += An[i -1][j];
				else if(j == i)//即數(shù)組每列最后一個沒有正上方的值，直接加左上值即可 
					An[i][j] += An[i - 1][j - 1];
				else//其余情況加其左上右上的最大值 
				{
					int max1 =Max(An[i - 1][j - 1],An[i - 1][j]); 
					An[i][j] += max1;
				}
			}
		}
	}
	//上面執(zhí)行完后，An數(shù)組每個值表示頂點到該位置路程最大值
	//向左下走的次數(shù)與向右下走的次數(shù)相差不能超過 1,即輸出第n行最中間二個的最大值
	//注意分行數(shù)的奇偶
	if(n%2==1)  
		printf("%d\n",An[n-1][(n-1)/2]);
	else 
		printf("%d\n",Max(An[n-1][(n-1)/2],An[n-1][(n-1)/2+1]));
	
	return 0;
}

4.藍橋OJ 3367：破損的樓梯（迭代法）

這個題使用一種遞推的思路：

對于每一個要到的樓梯：

求到這里有幾種方案，

就考慮到這個位置的前一步：從上一格位置A來或從上兩格的位置B來

發(fā)現(xiàn)，無論從A還是B來，都分別只有一種方案

所以，歸納出規(guī)律：方案數(shù)（位置n） = 方案數(shù)（位置n-1）+ 方案數(shù)（位置n - 2）

由此得到狀態(tài)轉移方程：????dp[i]?=?(dp[i?-?1]?+?dp[i?-?2])?%?p;

#include<bits/stdc++.h>
using namespace std;

using ll = long long ;
const int N = 1e5 + 9;
const ll p = 1e9 + 7;
ll dp[N];

bool broken[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin >> n >> m;
	
	for(int i = 1;i <= m;i ++){
		int  x;cin >> x;
		broken[x] = true;
	}
	
	dp[0] = 1;
	if(!broken[1])dp[1] = 1;
	for(int i = 2;i <= n; ++i)
	{
		if(broken[i])continue;
		dp[i] = (dp[i - 1] + dp[i - 2]) % p;
	}
	
	cout << dp[n] << endl;
	
	return 0;
}

5.藍橋OJ 3423：安全序列（迭代法）

這題與上一題類似但有不同：

考慮有n個位置的總方案數(shù)，位置n可以有桶可以沒桶，每一個位置都可以有桶或沒桶

把問題劃分為從第幾個位置開始沒桶的n種情況? （不重不漏）

所以方案總數(shù) == 方案數(shù)（第一個位置開始沒桶）+ 方案數(shù)（第二個位置開始沒桶）+ 方案數(shù)（第三個位置開始沒桶）+ ……+方案數(shù)（第n個位置開始沒桶）

再考慮怎么求從第 i 個位置開始沒桶（位置 i 擺最后的桶）的方案數(shù)：

發(fā)現(xiàn)既然這個位置有了桶，因為要間隔k，這個位置 - k 之前的每一個位置有桶，

下一步都可以到當前狀態(tài)，問題被進一步劃分。

歸納出規(guī)律：該方案數(shù) == 起始位置到這個位置前k個位置開始沒桶的情況的方案數(shù)之和

設置狀態(tài)dp[i]表示以位置i結尾的方案總數(shù)，

歸納出狀態(tài)轉移方程：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 9,p = 1e9 + 7;

ll dp[N],prefix[N];

int main()
{
	int n,k;cin >> n >> k;
	dp[0] = prefix[0] = 1;  //可能存在全都不放的情況
	for(int i = 1;i <= n;i ++)
	{
		if(i - k - 1 < 1)dp[i] = 1;
		else dp[i] = prefix[i - k - 1];
		prefix[i] = (prefix[i - 1] + dp[i]) % p;
	}
	cout << prefix[n] << endl;
	return 0;
}

6.藍橋OJ 389：擺花（二維DP）（迭代法）

對于每一個到達一個位置并種了某種花的情況，

方案數(shù)都是先種上一個位置并種了少用一種花的方案數(shù)，

具體來說：

這個方案數(shù)就是：保持種到相同位置，這最后一種花種了多少盆的所有情況的方案數(shù)之和

設狀態(tài)dp[i][j]表示到第i種花為止（不一定以第i種花結尾），到第j個位置（1-j都放了花）的情況下的總方案數(shù)：

圖解：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

歸納出狀態(tài)轉移方程：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
using ll = long long;
const ll p = 1e6 + 7;
ll a[N],dp[N][N];

int main()
{
	int n,m; cin >> n >> m;
	for(int i = 1;i <= n; i ++)cin >> a[i];
	
	dp[0][0] = 1;
	
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 0;j <= m;j ++)
		{
			for(int k = 0;k <= a[i] && k <= j; k ++){
				dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % p;
			}
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}

7.藍橋OJ 3362：建造房屋（二維DP）（迭代法）

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

#include <iostream>
using namespace std;
using ll=long long;
const ll M=1e9+7;
const int N=1000;
ll dp[N][N]; //dp[j][k]表示截至到第j行，第k個房子的方案數(shù)
int main()
{
	int n,m,k;cin>>n>>m>>k;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			for(int s=1;s<=m&&s<=j-i+1;s++)
				dp[i][j]=(dp[i-1][j-s]+dp[i][j])%M;
		}
	}
	ll ans=0;
	for(int i=1;i<=k;i++)
		ans+=dp[n][i];
	cout<<(ans)%M;
	return 0;
}

?8.最長上升子序列（LIS）

?LIS（Longest Increasing Subsequence最長上升子序列）是一個經典的DP模型

樸素LIS模型：時間復雜度O（n^2）

二分LIS模型：時間復雜度O（nlogn）

?LIS指一個序列中，按照原順序選出若干個不一定連續(xù)的元素組成的序列，要求序列遞增

求解：

設dp[i]表示1~i中以a[i]結尾的最長上升子序列的長度

狀態(tài)轉移方程：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

圖解：

藍橋OJ 1358：藍橋勇士

狀態(tài)轉移方程：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 9;
int a[N],dp[N];

int main()
{
    int n ;cin >> n;
	for(int i = 1;i <= n;i ++)cin >> a[i];
	
	for(int i = 1;i <= n;i ++)
	{
		dp[i] = 1;
		for(int j = 1;j < i;j ++)
		{
			if(a[i] > a[j])dp[i] = max(dp[i],dp[j] + 1);
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i ++)ans = max(ans,dp[i]);
	cout << ans << endl;
	return 0;
}

藍橋OJ 742：合唱隊形

設狀態(tài)dpl[i]表示1~i的最長上升子序列的長度，dpr[i]表示反向的n~i的最長上升子序列的長度，求出兩個dp數(shù)組后，計算出最大的 dpl[i] + dpr[i] - 1 即可。

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int N = 150;
int a[N],dpl[N],dpr[N];

int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n; ++i)cin >> a[i];
	for(int i = 1;i <= n;i ++)
	{
		dpl[i] = 1;
		for(int j = 1;j < i;j ++)if(a[i] > a[j])dpl[i] = max(dpl[i],dpl[j] + 1);
	}
	for(int i = n;i >= 1;--i)
	{
		dpr[i] = 1;
		for(int j = i + 1;j <= n;j ++)if(a[i] > a[j])dpr[i] = max(dpr[i],dpr[j] + 1);
	}
	
	int ans = n;
	for(int i = 1;i <= n;i ++)ans = min(ans,n - (dpl[i] + dpr[i] - 1));
	
	cout << ans << endl;
	return 0;
}

9.最長子序列（LCS）

LCS（Longest Common Subsequence 最長公共子序列）是一個經典的DP模型。

復雜度：O（n^2）

LCS問題是給定兩個序列A和B，求它們的最長公共子序列。

求解：設dp[i][j]表示A[1~i]序列和B[1~j]序列中的最長公共子序列長度。

藍橋OJ 1189：最長公共子序列

狀態(tài)轉移方程：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

解釋：

當a[i] == b[i]，將它們插入到LCS后面，使長度變長1

當a[i]!=b[i]，說明此時LCS不會變長，就要從dp[i-1][j]和dp[i][j-1]取大

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
int n,m,a[N],b[N],dp[N][N];
int main(){
	int n,m;cin >> n >> m;
	for(int i = 1;i <= n;i ++)cin >> a[i];
	for(int i = 1;i <= m;i ++)cin >> b[i];
	
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= m;j ++)
		{
			if(a[i] == b[j])dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
		}
	}
	cout << dp[n][m] << endl;
	
	return 0;
}

另：求出其中一個最長的子序列

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
int n,m,a[N],b[N],dp[N][N];
int main(){
	int n,m;cin >> n >> m;
	for(int i = 1;i <= n;i ++)cin >> a[i];
	for(int i = 1;i <= m;i ++)cin >> b[i];
	
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= m;j ++)
		{
			if(a[i] == b[j])dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
		}
	}
	cout << dp[n][m] << endl;
	
	return 0;
}

10.藍橋OJ 3349：可構造的序列總數(shù)（二維DP）

dp[i][j]表示在位置i處以數(shù)字j結尾的序列總數(shù)。

發(fā)現(xiàn)，dp[i][?]處的上一步一定是dp[i-1][?]

現(xiàn)討論 j 的取值：

對于每一個 j ，遍歷每一個小于 j 的數(shù)，得到兩個因子，

因為題目中的倍數(shù)限制，所以上一步一定是有這兩個因子的情況。（完全平方單獨討論）

狀態(tài)轉移方程：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4000;
const ll mod = 1e9+7;
int n, k;
ll dp[N][N], two[N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> k >> n;
	for(int i = 1; i <= k; ++ i)
	{
		dp[1][i] = 1;
	}
	if(n == 1)
	{
		cout << k;
		return 0;
	}
	for(int i = 2; i <= n; ++ i)
	{
		for(int j = 1; j <= k; ++ j)
		{
			for(int t = 1; t * t <= j; ++ t)
				// 這里的優(yōu)化是關鍵，如果直接枚舉從1到j會 t， 而對每一個小于根號j的因數(shù)當你找出他的時候就能找到一個對應的大于根號j的因數(shù) 因此時間復雜度從O(n3)優(yōu)化到O(n2 * 根號n） 大概2e8 極限能過
			{
				if(t * t == j) dp[i][j] = (dp[i][j] + dp[i-1][t]) % mod;
				else if(j % t == 0) dp[i][j] = (dp[i][j] + dp[i-1][t] + dp[i-1][j/t]) % mod;
				
			}
		}
	}
	ll ans = 0;
	for(int i = 1; i <= k; ++ i) ans = (ans + dp[n][i]) % mod;
	cout << ans;
	return 0;
}

11.藍橋OJ 3349：最快洗車時間（二維DP）

這題很容易想到用貪心的思想解決，但是這無法保證兩個地方時間盡可能的相近。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;cin >> n;
	
	vector<int>a(n);
	for(int k = 0;k < n;k ++)cin >> a[k];
	//sort(a.begin(),a.end());
	for(int l = n - 1;l >= 0;l--){
		for(int x = 0;x < l;x ++)
		{
			if(a[x+1] < a[x])swap(a[x+1],a[x]);
		}
	}
	int suma=0;
	int sumb=0;
	int i=0,j=n-1;
	while(i!=j)
	{
	    sumb+=a[j];
		j--;
		while(suma<sumb)
		{
			suma+=a[i];
			if(i==j)break;
		
			i++;

		}
	}
	cout << max(suma,sumb) << endl;
	
	return 0;
}

考慮這個反例：

算法學習記錄：動態(tài)規(guī)劃,學習,動態(tài)規(guī)劃,算法

因此只能使用動態(tài)規(guī)劃枚舉所有可能：

正解：文章來源地址http://www.zghlxwxcb.cn/news/detail-822360.html

//本題的難點仍在于狀態(tài)轉移方程的設計與列寫
//由于兩臺機器完全相同，若總時間為sum，其中一臺洗車時間為i，則另一臺洗車時間為sum-i
//i與sum-i中的較大值即為最終答案
//故本題可以只考慮其中一臺機器，枚舉其所有洗車方案(可能花費的洗車時間)并使用動態(tài)規(guī)劃驗證該方案是否可行
//最終遍歷該臺機器所有可行的洗車方案，計算并比較出最終的洗車時間 
//注：本題有一種錯誤解法，即把數(shù)組排序以后令兩臺機器分別從頭和尾開始往中間遍歷洗車
//這種解法是基于貪心思想的，但它并不能保證兩臺機器的洗車時間盡可能的接近，因此無法得出正確答案
//事實上在允許的時間復雜度內，本題并不存在直接找出最佳洗車方案的算法，
//只能使用動態(tài)規(guī)劃來驗證每一種洗車方案,然后比較得出最終答案 
#include <bits/stdc++.h>

using namespace std;

int Time[109];
bool dp[109][10009];
//dp[i][j]表示只考慮前i輛車(每輛車可能洗或不洗)，能否使總洗車時間為j，若能則為true 

int main()
{
	int N;
	int sum=0;
	int ans=1e9;
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		cin>>Time[i];
		sum=sum+Time[i];//計算總洗車時間 
	}
	
	for(int i=0;i<=N;i++)dp[i][0]=true;//初始化，若該機器總洗車時間為0，必然能做到 
	
	for(int i=1;i<=N;i++)//遍歷每一種可能的洗車方案，依次考慮前1~N輛車 
	{
		for(int j=0;j<=sum;j++)//對于每一種洗車方案，遍歷該機器所有可能的洗車時間，可能花0~sum分鐘 
		{
			//若洗前i-1輛車的時間為j-Time[i],則洗前i輛車的時間可以是j(洗第i輛車)
			//若洗前i-1輛車的時間為j，則洗前i輛車的時間也可以是j(不洗第i輛車)
			//兩種情況滿足其一，dp[i][j]即為true
			//此處注意j-Time[i]要大于等于0，故分開寫(合在一起寫會有一個測試點錯誤) 
			dp[i][j]=dp[i-1][j];
			if(j>=Time[i])dp[i][j]=dp[i][j] | dp[ i - 1 ][ j - Time[i] ];    
		}    
	} 
	
	for(int i=1;i<=sum;i++)//遍歷其中一臺機器所有可能的洗車時間1~sum 
	{
		if(dp[N][i])//若對于前N輛車，該機器洗車時間可以是i 
		{
			int tmp=max(sum-i,i);//則對于該洗車方案，兩臺機器洗車完成的時間是sum-i和i之間的較大值 
			if(tmp<ans)ans=tmp;//比較得出所有洗車方案所花時間的最小值 
		}
	}
	cout<<ans<<endl;
	return 0;
}

到了這里，關于算法學習記錄：動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！