原題鏈接
動態(tài)規(guī)劃基本原理
動態(tài)規(guī)劃（Dynamic Programming，簡稱 DP）是一種通過將原問題分解為相互重疊的子問題并只解決一次的方法來解決問題的算法優(yōu)化技術(shù)。動態(tài)規(guī)劃通常用于優(yōu)化遞歸問題，通過存儲子問題的解來避免重復(fù)計算，從而顯著提高算法的效率。
基本思想
動態(tài)規(guī)劃的基本思想是將原問題劃分為若干個子問題，通過解決子問題得到原問題的解。在這個過程中，動態(tài)規(guī)劃使用了最優(yōu)子結(jié)構(gòu)和重疊子問題兩個關(guān)鍵性質(zhì)。
-
最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解可以通過子問題的最優(yōu)解來構(gòu)造。即，全局最優(yōu)解包含了所有局部最優(yōu)解。
-
重疊子問題：在遞歸求解過程中，對于一些子問題的解會被多次使用。為了避免重復(fù)計算，我們可以將子問題的解存儲起來，后續(xù)直接使用，這就是動態(tài)規(guī)劃中的記憶化。
基本步驟
動態(tài)規(guī)劃通常包含以下基本步驟：
-
定義狀態(tài)：明確定義問題的狀態(tài)，找出問題中具有變化的量，并將其表示為狀態(tài)。狀態(tài)是原問題和子問題中變化的量。
-
找到狀態(tài)轉(zhuǎn)移方程：建立狀態(tài)之間的關(guān)系，即如何由小的子問題推導(dǎo)出大問題的解。狀態(tài)轉(zhuǎn)移方程是動態(tài)規(guī)劃的核心。
-
初始化：設(shè)置問題的初始值，通常是最簡單的情況，這是遞歸或迭代的終止條件。
-
遞推計算：按照狀態(tài)轉(zhuǎn)移方程，從初始狀態(tài)開始遞推計算，直到計算出原問題的解。
-
解決原問題：得到原問題的解，這通常是在狀態(tài)中已經(jīng)計算得到的值。
應(yīng)用領(lǐng)域
動態(tài)規(guī)劃廣泛應(yīng)用于各個領(lǐng)域，包括但不限于：
- 優(yōu)化問題：如最短路徑、最長子序列、背包問題等。
- 計算問題：如斐波那契數(shù)列、組合數(shù)等。
- 決策問題：如股票買賣、任務(wù)調(diào)度等。
總的來說，動態(tài)規(guī)劃通過將復(fù)雜問題分解為簡單的子問題，并有效地保存子問題的解，從而在時間和空間上實現(xiàn)了高效的問題求解。
找到最大開銷的子字符串算法解析
問題描述
給定一個字符串 s，一個字符互不相同的字符串 chars 和一個長度與 chars 相同的整數(shù)數(shù)組 vals。子字符串的開銷是一個子字符串中所有字符對應(yīng)價值之和，空字符串的開銷是 0。
字符的價值定義如下：
- 如果字符不在字符串
chars中，那么它的價值是它在字母表中的位置（下標(biāo)從 1 開始）。 - 如果字符在
chars中的位置為i，那么它的價值就是vals[i]。
問題要求返回字符串 s 的所有子字符串中的最大開銷。
思路
題目要求找到最大開銷的子字符串，我們可以使用動態(tài)規(guī)劃的思路解決。在這里，我們使用一個一維數(shù)組 dp 來記錄以字符串 s 的每一位結(jié)尾的最大開銷。
狀態(tài)定義
我們定義 dp[i] 為以字符串 s 的第 i 位結(jié)尾的最大開銷。
狀態(tài)轉(zhuǎn)移
狀態(tài)轉(zhuǎn)移方程為 dp[i] = max(dp[i - 1] + char_val, char_val)，其中 char_val 是第 i 個字符對應(yīng)的開銷值。
代碼實現(xiàn)
class Solution:
def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
char_idx = {}
for idx, char in enumerate(chars):
char_idx[char] = idx
n = len(s)
dp = [0] * n
dp[0] = vals[char_idx[s[0]]] if s[0] in char_idx else ord(s[0]) - ord('a') + 1
ans = max(dp[0], 0)
for i in range(1, n):
new_char_val = vals[char_idx[s[i]]] if s[i] in char_idx else (ord(s[i]) - ord('a') + 1)
dp[i] = max(dp[i - 1] + new_char_val, new_char_val)
ans = max(ans, dp[i])
return ans
示例分析
示例 1
s = "adaa"
chars = "d"
vals = [-1000]
solution = Solution()
result = solution.maximumCostSubstring(s, chars, vals)
print(result) # Output: 2
解釋：字符 “a” 和 “d” 的價值分別為 1 和 -1000。最大開銷子字符串是 “aa”，它的開銷為 1 + 1 = 2。2 是最大開銷。
示例 2
s = "abc"
chars = "abc"
vals = [-1,-1,-1]
solution = Solution()
result = solution.maximumCostSubstring(s, chars, vals)
print(result) # Output: 0
解釋：字符 “a”，“b” 和 “c” 的價值分別為 -1，-1 和 -1。最大開銷子字符串是 “”，它的開銷為 0。0 是最大開銷。
復(fù)雜度分析
時間復(fù)雜度
遍歷字符串 s 一次，每次更新 dp[i] 的操作為 O(1)，因此總時間復(fù)雜度為 O(n)。文章來源：http://www.zghlxwxcb.cn/news/detail-773153.html
空間復(fù)雜度
使用了額外的空間來存儲 dp 數(shù)組和 char_idx 字典，因此空間復(fù)雜度為 O(n)。文章來源地址http://www.zghlxwxcb.cn/news/detail-773153.html
到了這里，關(guān)于【算法思考記錄】動態(tài)規(guī)劃入門！力扣2606. 找到最大開銷的子字符串【Python3、動態(tài)規(guī)劃】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
