動態(tài)規(guī)劃第十二周也寫了一部分，只不過忘記放上去了。

新的一年啦，看到這里砸個祝福：新年快樂，身體健康，考試順利，心想事成！

2024/1/6? ? ? ? 周六

藍(lán)橋杯2012省賽?????微生物增殖（簡單）

【解題思路】

其實(shí)新出生半分鐘吃一個是干擾項(xiàng)，實(shí)際上是一分鐘吃一個

【參考代碼】

#include <iostream>
using namespace std;
int main()
{
  // 請?jiān)诖溯斎肽拇a
  int x = 10, y = 90;
  for(int time = 1 ; time <= 60 ; time++) 
  {
        y -= x; //Y被x個x吃掉，一分鐘吃一次
        if(time % 2 == 0) //Y每隔2分鐘分裂一次
          y *= 2;
        
        if(time % 3 == 0) //X每隔3分鐘分裂一次
          x *= 2;
  }
  cout << y;
  return 0;
}

【輸出結(jié)果】?

動態(tài)規(guī)劃的思想

分為線性DP，狀態(tài)壓縮DP，數(shù)位DP，樹形DP。

動態(tài)規(guī)劃解題步驟

基本步驟分為以下四步

(1)轉(zhuǎn)換成子問題。對于動態(tài)規(guī)劃,最重要的是把一個大的問題劃分成若干子問題,即進(jìn)行問題降階,通過逐級降階將問題簡化,從而實(shí)現(xiàn)問題的求解。

(2)轉(zhuǎn)移方程,把問題方程化。

(3)按照實(shí)際邏輯設(shè)置邊界情況和初始條件。

(4)確定計算順序并求解。

動態(tài)規(guī)劃與分治法最大的差別

適合于用動態(tài)規(guī)劃法求解的問題, 經(jīng)分解后得到的子問題往往不是互相孤立的

(即下一子問題的求解是建立在上一子問題的解的基礎(chǔ)上而進(jìn)行的進(jìn)一步求解)。

經(jīng)典實(shí)例

背包問題

01背包問題

題目鏈接

題目：有一個背包可以裝一定重的物品,如何裝物品才能使得背包的價值最大? 背包能裝的重量是 10 斤，可以裝的物品有以下幾種：

??? 礦泉水(重5斤,價值 10)

??? 書(重3斤,價值5)

??? 小吃(重4斤,價值 8)

??? 水果(重4斤,價值 9)

??? 相機(jī)(重2斤,價值6)

請問:攜帶哪些物品時價值最高?

【參考代碼】：

#include <iostream>
using namespace std;
#include <iomanip> //用于setw函數(shù)



int main()
{
??? int n, m;? //物品個數(shù)，背包總重量
??? int value[100][100];
??? int v[100], w[100];
??? cin >> n >> m;
??? for (int i = 1; i <= n; i++)
??????? cin >> w[i] >> v[i];? //重量，價值

??? for (int j = 0; j <= m; j++)
??????? value[0][j] = 0;

??? for (int i = 1; i <= n; i++)
??? {
??????? value[i][0] = 0;
??????? for (int j = 1; j <= m; j++)
??????? {
???????????? value[i][j] = value[i - 1][j];
???????????? if (j >= w[i])
???????????????? //狀態(tài)轉(zhuǎn)移方程
? ?????????????? value[i][j] = max(value[i - 1][j], value[i - 1][j - w[i]] + v[i]);
??????? }
??? }
??? cout << "01背包各狀態(tài)轉(zhuǎn)換表：" << endl;
??? for (int i = 0; i <= n; i++)
??? {
??????? for (int j = 0; j <= m; j++)
???????????? cout << setw(3) << value[i][j]; //隔3格輸出
??????? cout << endl;
??? }

??? cout << "背包能裝的最大價值為：" << value[n][m];

}

【運(yùn)行結(jié)果】：

優(yōu)化后的01背包：

#include <iostream>
using namespace std;

int f[1001], v[1001], w[1001];

int main()
{
	int n, m;  //物品個數(shù)，背包總重量
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];  //體積，價值
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= v[i]; j--)
		{
			//狀態(tài)轉(zhuǎn)移方程
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}

	cout << f[m];
}

?

完全背包問題

題目鏈接

【參考代碼】：

#include <iostream>
using namespace std;

int n, m, f[1001], v[1001], w[1001];

int main(){
    cin >> n >> m;
    for(int i=1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }
    for(int i=1; i <= n; i++)
        for(int j = v[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[m];
}

【輸出結(jié)果】

多重背包

題目鏈接

參考代碼：

#include <iostream>
using namespace std;

int n, m, f[1001], v[1001], w[1001], l[1001];

int main()
{
    cin >> n >> m;
    for(int i=1; i <= n; i++)
        cin >> v[i] >> w[i] >> l[i];
    for(int i=1; i <= n; i++)
        for(int k=1; k <= l[i]; k++)
            for(int j=m; j>= v[i]; j--)
                f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
        
}

【輸出結(jié)果】：

分組背包

題目鏈接

【參考代碼】

此代碼未通過100%題目測試點(diǎn)

#include <iostream>
#include <vector>
using namespace std;

//ai, bi, ci, 物品重量，利用價值，所屬組數(shù)
int a[1001], v[1001], w[1001], f[1001];
vector<int> c[1001];

int main()
{
    //兩個數(shù)m, n，表示一共有n件物品，總重量為m
    int m, n;
    cin >> m >> n;
    int i, j;
    for(i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i] >> a[i];
        c[a[i]].push_back(i);
    }
    for(i = 1; i <= 1000; i++)
        for(j = m; j; j--)
            for(auto k : c[i])
            {
                if(v[k] <= j)
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
            }
    cout << f[m];
}

for(auto k : c[i])?是一個基于范圍的for循環(huán)，在C++中常見。這里是對它的分解：

• auto: 這是一個自動類型推導(dǎo)關(guān)鍵字。在基于范圍的for循環(huán)中，編譯器會自動從c[i]中獲取元素類型，并推斷出k的類型。
• k: 這是循環(huán)中當(dāng)前元素的臨時變量名。在每次循環(huán)迭代時，k將持有c[i]中的一個元素。
• for(auto k : c[i]): 整體而言，這個循環(huán)從c[i]作為起點(diǎn)開始遍歷中的每一個元素，并將每個元素賦值給變量k。

二維背包

爬樓梯

題目鏈接

參考代碼：

int jumpFloor(int number) {
        if(number == 1)
            return 1;
        if(number == 2)
            return 2;
        return jumpFloor(number - 1) + jumpFloor(number - 2);
}

斐波那契數(shù)列的實(shí)際應(yīng)用

石子合并（區(qū)間DP）

題目鏈接

【參考代碼】

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

long long a[201] = {0}, s[201] = {0}, f[201][201]; // 定義數(shù)組a、s和f

// 遞歸函數(shù)solve，用于計算最小分割代價
long long solve(int l, int r)
{
    if(f[l][r] != -1) // 如果已經(jīng)計算過該子問題的解，直接返回結(jié)果
       return f[l][r];
	if(l == r) // 如果左右邊界相等，說明只有一個元素，不需要分割，返回0
		return 0;
	long long ans = 1 << 30; // 初始化最小分割代價為一個較大的值 2的30次方
	for(int m = l; m < r; m++) // 遍歷所有可能的分割點(diǎn)m
	// 計算左右兩部分的最小分割代價，并取較小值
		ans = min(ans, solve(l, m) + solve(m+1, r)); 
	return f[l][r] = ans + s[r] - s[l-1]; // 將計算得到的最小分割代價存儲到f數(shù)組中，并返回結(jié)果
}

int main()
{
    memset(f, 255, sizeof(f)); // 初始化f數(shù)組為-1，表示未計算過任何子問題的解
	int n;
	cin >> n; 
	for(int i=1; i<=n; i++) 
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 計算前綴和數(shù)組s
	}
    cout << solve(1, n); // 調(diào)用solve函數(shù)計算最小分割代價，并輸出結(jié)果
	//cout << f[1][n]; 這個就是最終答案
}

f[1][n]是最終答案，可以看到矩形右上角為最終答案f[1][n]

Q：9是怎么來的？

A：在5和3之間選一個最小值，前綴和數(shù)組是1,3,6。加上前綴和數(shù)組的最大值6

1. ans?=?min(ans,?solve(l,?m)?+?solve(m+1,?r));
2. return?f[l][r]?=?ans?+?s[r]?-?s[l-1];

Q：14怎么來的？

A：5和7選一個最小值，得出5。前綴和數(shù)組是1,3,6,10。f[2][4] = 14 = 5 + 10 (s[r]) – 1 (s[l-1])

9和14選一個最小值，加上前綴和數(shù)組的最大值10

1. ans?=?min(ans,?solve(l,?m)?+?solve(m+1,?r));
2. return?f[l][r]?=?ans?+?s[r]?-?s[l-1];

• 可以看出，若不加終止條件，會調(diào)用很多次遞歸函數(shù)，多次重復(fù)計算。優(yōu)化后，用一個二維數(shù)組保存

最長公共子序列

題目鏈接

參考代碼

class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
     {
        //最長上升子序列
        int ans = 0;
        int dp[2501] = {0};
        int n = nums.size();
        //需要從0開始，不然會報錯：爆棧
        for(int i=0; i < n; i++)
        {
            dp[i] = 1;
            for(int j=0; j < i; j++)
            {
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        for(int i=0; i < n; i++)
        {
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

最長公共子序列

題目鏈接

參考代碼

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length();
        int m = text2.length();
        int f[1001][1001];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if(text1[i-1] == text2[j-1]) //i, j從1開始，string從1開始，要減1
                //if(text1[i] == text2[j])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
        return f[n][m];
    }
};

運(yùn)行結(jié)果

文章來源地址http://www.zghlxwxcb.cn/news/detail-789323.html

最長回文子串

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