CSDN官方推出創(chuàng)作助手InsCode AI很多天了，有心人都能發(fā)現(xiàn)，在寫作界面的右上角多了一個(gè)創(chuàng)作助手的浮動(dòng)按鈕，點(diǎn)擊后出現(xiàn)如下界面：

現(xiàn)階段是“限免”狀態(tài)，不好好利用它來創(chuàng)作，就有點(diǎn)辜負(fù)CSDN官方大佬們的良苦用心了。

以主題“動(dòng)態(tài)規(guī)劃法”寫一篇博客，以下是我用創(chuàng)作助手InsCode AI輔助寫作的全過程，教你分分鐘搞定一篇“好”文章！

用法簡(jiǎn)介：

1. 以主題線索列舉幾個(gè)提問，比如“何為動(dòng)態(tài)規(guī)劃法”、“詳細(xì)介紹一下動(dòng)態(tài)規(guī)劃算法”、“寫一個(gè)動(dòng)態(tài)規(guī)劃算法并做大量注解”。

2. 把InsCode AI的答案插入寫作文本框，整理之后自擬各段文字的多級(jí)標(biāo)題。

3. 最后寫段文章小結(jié)，插入目錄，添加插圖美化一下，保存草稿。

快速搞定一篇！正文如下：

目錄

動(dòng)態(tài)規(guī)劃法

定義

條件

步驟

簡(jiǎn)單實(shí)例

題目描述

算法實(shí)現(xiàn)

代碼實(shí)現(xiàn)?

進(jìn)階實(shí)例

題目描述

1. 基于遞推的自底向上方法

2. 基于記憶化搜索的自頂向下方法

本文小結(jié)

動(dòng)態(tài)規(guī)劃法

定義

全稱為 Dynamic Programming，縮寫為DP。是一種常用的解決多階段決策問題的數(shù)學(xué)算法。它通常用于求解具有某種最優(yōu)性質(zhì)的問題，比如最大值、最小值等等。

動(dòng)態(tài)規(guī)劃算法通?；谝粋€(gè)遞推公式以及一個(gè)或多個(gè)初始狀態(tài)。當(dāng)前子問題的解將由上一次子問題的解推出來。動(dòng)態(tài)規(guī)劃算法在處理問題時(shí)，會(huì)把子問題的解緩存起來，這樣以后再遇到同樣的子問題時(shí)可以直接查表而不必重新計(jì)算。這種方式可以避免重復(fù)計(jì)算，減少計(jì)算量，提高算法效率。

動(dòng)態(tài)規(guī)劃算法在求解各種經(jīng)濟(jì)、管理、信息、技術(shù)等方面的優(yōu)化問題中有廣泛應(yīng)用。

條件

一般來說，動(dòng)態(tài)規(guī)劃問題會(huì)滿足以下幾個(gè)條件：

1. 有重疊子問題：即一個(gè)問題的子問題是重復(fù)的，需要不斷進(jìn)行重復(fù)計(jì)算。

2. 子問題具有最優(yōu)子結(jié)構(gòu)：即子問題之間相互獨(dú)立，且子問題的最優(yōu)解能夠推導(dǎo)出原問題的最優(yōu)解。

3. 無后效性：即某個(gè)狀態(tài)一旦確定，就不受之后決策的影響。

步驟

動(dòng)態(tài)規(guī)劃（Dynamic Programming）是一種解決多階段決策過程最優(yōu)化問題的數(shù)學(xué)方法，它將原問題分解為相對(duì)簡(jiǎn)單的子問題，并采用遞推的方式求解子問題，最終得到原問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃算法分為兩種類型：一種是基于記憶化搜索的自頂向下的方法，另一種是基于遞推的自底向上的方法。在這兩種方法中，都需要定義狀態(tài)和狀態(tài)轉(zhuǎn)移方程，以確定子問題間的遞推關(guān)系。具體來說，我們可以通過以下步驟來設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法：

1. 確定狀態(tài)：找到問題中的最簡(jiǎn)單的子問題，列出狀態(tài)表示，比如最大子序列問題中，狀態(tài)可能表示為以第i個(gè)數(shù)為結(jié)尾的最大子序列和。

2. 確定狀態(tài)轉(zhuǎn)移方程：列出狀態(tài)轉(zhuǎn)移方程，即當(dāng)前子問題的最優(yōu)解如何由前一個(gè)子問題的最優(yōu)解得到。

3. 確定初始狀態(tài)：確定所有子問題中最簡(jiǎn)單的狀態(tài)的解，通常是邊界狀態(tài)。

4. 確定計(jì)算順序：根據(jù)狀態(tài)轉(zhuǎn)移方程，確定計(jì)算的順序，通常是按照狀態(tài)的維度進(jìn)行計(jì)算。

5. 優(yōu)化內(nèi)存空間：如果狀態(tài)轉(zhuǎn)移只與前一個(gè)狀態(tài)有關(guān)，則可以不必緩存所有狀態(tài)，只需要緩存前一個(gè)狀態(tài)即可。

簡(jiǎn)單實(shí)例

下面以 LeetCode 509題 "斐波那契數(shù)" 為例，給出一個(gè)動(dòng)態(tài)規(guī)劃算法并加上詳細(xì)的注解。

題目描述

斐波那契數(shù)，通常用 F(n) 表示，形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。即：

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), 其中 n > 1.

示例 1:

輸入: 2 輸出: 1 解釋: F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2:

輸入: 3 輸出: 2 解釋: F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3:

輸入: 4 輸出: 3 解釋: F(4) = F(3) + F(2) = 2 + 1 = 3.

算法實(shí)現(xiàn)

1. 確定狀態(tài)：根據(jù)題目描述，可以定義一個(gè)數(shù)組 dp[] 來表示斐波那契數(shù)列中前n個(gè)數(shù)字的值，dp[i]表示斐波那契數(shù)列中第i個(gè)數(shù)字的值。

2. 確定狀態(tài)轉(zhuǎn)移方程：根據(jù)斐波那契數(shù)列的定義，dp[i] = dp[i-1] + dp[i-2]，其中i > 1。

3. 確定初始狀態(tài)：根據(jù)斐波那契數(shù)列的定義，dp[0] = 0，dp[1] = 1。

4. 確定計(jì)算順序：從左到右依次計(jì)算dp[2]、dp[3]、……、dp[n]。

5. 優(yōu)化內(nèi)存空間：由于狀態(tài)轉(zhuǎn)移只與前兩個(gè)狀態(tài)有關(guān)，因此可以只用兩個(gè)變量來記錄前兩個(gè)狀態(tài)的值，不必緩存所有狀態(tài)。

代碼實(shí)現(xiàn)?

下面是完整的算法實(shí)現(xiàn)，每一行都有注釋說明。

package main

import "fmt"

func fib(n int) int {
	if n < 2 {   // 如果n為0或1，直接返回n
		return n
	}
	dp := [2]int{0, 1}   // 定義初始狀態(tài)，dp[0]表示F(0)，dp[1]表示F(1)
	for i := 2; i <= n; i++ {   // 從2到n按照狀態(tài)轉(zhuǎn)移方程求解
		dp_i := dp[0] + dp[1]   // 計(jì)算dp[i]，即F(i)
		dp[0] = dp[1]   // 更新前兩個(gè)狀態(tài)
		dp[1] = dp_i
	}
	return dp[1]   // 返回最終結(jié)果
}

func main() {
	fmt.Println(fib(2)) // 1
	fmt.Println(fib(3)) // 2
	fmt.Println(fib(4)) // 3
}

該算法的時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。時(shí)間復(fù)雜度線性，空間復(fù)雜度常數(shù)級(jí)別，因此在實(shí)際應(yīng)用中較為實(shí)用。

進(jìn)階實(shí)例

下面以 LeetCode 1143題 "最長(zhǎng)公共子序列" （LCS）為例，運(yùn)用動(dòng)態(tài)規(guī)劃兩種類型分別實(shí)現(xiàn)：

題目描述

給定兩個(gè)字符串?text1?和?text2，返回這兩個(gè)字符串的最長(zhǎng)?公共子序列?的長(zhǎng)度。如果不存在?公共子序列?，返回?0?。

一個(gè)字符串的?子序列?是指這樣一個(gè)新的字符串：它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

• 例如，"ace"?是?"abcde"?的子序列，但?"aec"?不是?"abcde"?的子序列。

兩個(gè)字符串的?公共子序列?是這兩個(gè)字符串所共同擁有的子序列。

示例 1：

輸入：text1 = "abcde", text2 = "ace" 
輸出：3  
解釋：最長(zhǎng)公共子序列是 "ace" ，它的長(zhǎng)度為 3 。

示例 2：

輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長(zhǎng)公共子序列是 "abc" ，它的長(zhǎng)度為 3 。

示例 3：

輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個(gè)字符串沒有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1?和?text2?僅由小寫英文字符組成。

1. 基于遞推的自底向上方法

在該方法中，我們從子問題開始，依次計(jì)算出所有的子問題，最終得到原問題的答案。具體地，我們使用一個(gè)數(shù)組來記錄子問題的答案，然后根據(jù)子問題的結(jié)果計(jì)算更大的問題的答案，直到求解出原問題的答案。

例如，在求解兩個(gè)字符串的最長(zhǎng)公共子序列問題時(shí)，我們可以定義一個(gè)二維的數(shù)組dp[i][j]，表示計(jì)算字符串1的前i個(gè)字符和字符串2的前j個(gè)字符的最長(zhǎng)公共子序列。我們首先將數(shù)組中所有的元素初始化為0，然后依次遍歷字符串1和字符串2的所有字符，根據(jù)當(dāng)前字符是否相等來更新數(shù)組中的元素：

• 如果第i個(gè)字符和第j個(gè)字符相同，則最長(zhǎng)公共子序列長(zhǎng)度加1，即dp[i][j] = dp[i-1][j-1] + 1；
• 如果第i個(gè)字符和第j個(gè)字符不同，則最長(zhǎng)公共子序列長(zhǎng)度等于前一個(gè)狀態(tài)中兩個(gè)字符串中較長(zhǎng)的那個(gè)字符串的最長(zhǎng)公共子序列長(zhǎng)度，即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最終，dp[m][n]就是字符串1和字符串2的最長(zhǎng)公共子序列的長(zhǎng)度，其中m和n分別為兩個(gè)字符串的長(zhǎng)度。代碼如下：

package main

import "fmt"

func MaxLCS(s1, s2 string) int {
	m, n := len(s1), len(s2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[m][n]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	text1 := "abcde"
	text2 := "ace"
	fmt.Println(MaxLCS(text1, text2))
	text1 = "abc"
	text2 = "abc"
	fmt.Println(MaxLCS(text1, text2))
	text1 = "abc"
	text2 = "def"
	fmt.Println(MaxLCS(text1, text2))
}

2. 基于記憶化搜索的自頂向下方法

在該方法中，我們使用遞歸函數(shù)和一個(gè)備忘錄來實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃。遞歸函數(shù)的基本思想是把原問題劃分成若干個(gè)子問題，每個(gè)子問題都解決一次，然后將其結(jié)果緩存，避免重復(fù)計(jì)算。備忘錄記錄了已經(jīng)計(jì)算過的子問題的答案，如果當(dāng)前問題之前已經(jīng)被解決過，則直接返回備忘錄中的結(jié)果。

首先定義了一個(gè)?lcs?函數(shù)，用于遞歸尋找最長(zhǎng)公共子序列。在該函數(shù)中，我們需要傳入兩個(gè)字符串 s1 和 s2、以及當(dāng)前的遍歷下標(biāo)（i 和 j）和記憶化數(shù)組 memo。memo 用于存儲(chǔ)已經(jīng)遍歷過的字符串長(zhǎng)度信息，避免重復(fù)計(jì)算公共子序列，因?yàn)橛?jì)算公共子序列的遞歸過程中存在大量的重復(fù)計(jì)算，使用 memo 記錄已有的計(jì)算結(jié)果可以大大提高計(jì)算效率。在進(jìn)行計(jì)算前，我們首先判斷當(dāng)前查詢的兩個(gè)字符串是否為空，如果是，則直接返回 0。如果當(dāng)前條件已經(jīng)對(duì)應(yīng) memo 數(shù)組中的值，則直接返回對(duì)應(yīng)結(jié)果。

之后，我們通過比較當(dāng)前遍歷的 s1 和 s2 字符串的最后一個(gè)字符（即 i-1 和 j-1）是否相等，分別進(jìn)行判斷。如果相等，則將最后一個(gè)字符放入公共子序列中，長(zhǎng)度加 1，遞歸向前尋找下一個(gè)字符；如果不相等，則通過在 s1 中移去最后一個(gè)字符或在 s2 中移去最后一個(gè)字符，分別計(jì)算得到兩種情況下的公共子序列，并將它們的長(zhǎng)度比較大小，返回最大的那個(gè)長(zhǎng)度。

在?MaxLCS?函數(shù)中，我們定義了一個(gè) memo 數(shù)組，用于存儲(chǔ)已經(jīng)遍歷過的字符串長(zhǎng)度信息。在循環(huán)初始化 memo 數(shù)組時(shí)，我們將各個(gè)位置的值設(shè)為 -1，表示尚未進(jìn)行過計(jì)算。最后，我們將 s1 和 s2 的兩個(gè)尾部下標(biāo)（即 len(s1) 和 len(s2)）以及 memo 數(shù)組傳入?lcs?函數(shù)中，得到最終的最長(zhǎng)公共子序列長(zhǎng)度。

代碼如下：

package main

import "fmt"

func lcs(s1, s2 string, i, j int, memo [][]int) int {
	if i == 0 || j == 0 {
		return 0
	}
	if memo[i][j] != -1 {
		return memo[i][j]
	}
	if s1[i-1] == s2[j-1] {
		memo[i][j] = lcs(s1, s2, i-1, j-1, memo) + 1
	} else {
		memo[i][j] = max(lcs(s1, s2, i-1, j, memo), lcs(s1, s2, i, j-1, memo))
	}
	return memo[i][j]
}

func MaxLCS(s1, s2 string) int {
	memo := make([][]int, len(s1)+1)
	for i := range memo {
		memo[i] = make([]int, len(s2)+1)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	return lcs(s1, s2, len(s1), len(s2), memo)
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	text1 := "abcde"
	text2 := "ace"
	fmt.Println(MaxLCS(text1, text2))
	text1 = "abc"
	text2 = "abc"
	fmt.Println(MaxLCS(text1, text2))
	text1 = "abc"
	text2 = "def"
	fmt.Println(MaxLCS(text1, text2))
}

本文小結(jié)

動(dòng)態(tài)規(guī)劃是一種通過將原問題拆分成子問題來解決復(fù)雜問題的算法。在動(dòng)態(tài)規(guī)劃中，通過記錄之前計(jì)算的結(jié)果，可以避免重復(fù)的計(jì)算，從而提高算法效率。

在動(dòng)態(tài)規(guī)劃問題中，通常需要定義狀態(tài)，確定狀態(tài)轉(zhuǎn)移方程和邊界條件。通過狀態(tài)轉(zhuǎn)移方程可以將問題分解為規(guī)模更小的子問題，并將子問題的解決結(jié)果存儲(chǔ)在一個(gè)表格中，以方便后續(xù)的計(jì)算。

動(dòng)態(tài)規(guī)劃常用于解決最長(zhǎng)公共子序列、最長(zhǎng)遞增子序列、背包問題、字符串編輯距離等問題。在解決這些問題時(shí)，我們需要通過分析問題的特殊性質(zhì)，設(shè)計(jì)出符合實(shí)際情況的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。

需要注意的是，在設(shè)計(jì)狀態(tài)轉(zhuǎn)移方程時(shí)，需要注意計(jì)算順序，尤其是當(dāng)某個(gè)狀態(tài)的計(jì)算依賴于前面的多個(gè)狀態(tài)時(shí)，需要仔細(xì)排列計(jì)算順序，避免出現(xiàn)錯(cuò)誤的結(jié)果。

總之，動(dòng)態(tài)規(guī)劃是一種有效的算法思想，可以解決很多實(shí)際問題。雖然需要一定的思維難度和技巧，但是只要掌握了基本原理和方法，就可以靈活地應(yīng)用到各種場(chǎng)景中，解決各種問題。

整理完成后，先別急著發(fā)表，鼠標(biāo)移動(dòng)到最下方按鈕“保存草稿”，出現(xiàn)“保存并預(yù)覽”后點(diǎn)擊它，得到文章鏈接，復(fù)制粘貼到CSDN質(zhì)量分查詢頁面里查分：

https://www.csdn.net/qc

不錯(cuò)，果然是"好"文章！可以發(fā)表了，如果感覺本文有點(diǎn)幫助，請(qǐng)收藏點(diǎn)贊，寫個(gè)評(píng)論。謝謝！文章來源地址http://www.zghlxwxcb.cn/news/detail-452593.html

到了這里，關(guān)于CSDN官方創(chuàng)作助手InsCode AI 教你分分鐘搞定一篇好文章的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！