動態(tài)規(guī)劃問題基本解題步驟
- 設計狀態(tài)
- 寫出狀態(tài)轉移方程
- 設置初始狀態(tài)
- 處理非法狀態(tài)
- 執(zhí)行狀態(tài)轉移
- 后處理
- 返回最終結果
顯式轉移方程
- 斐波那契數(shù)列
- 階乘
隱式轉移方程
- 爬樓梯
- 爬樓梯最小花費
注意:對于隱式狀態(tài)轉移方程允跑,可以先從初始的幾個狀態(tài)列舉出來萤皂,看能不能看出規(guī)律
相關題目練習
劍指 Offer 10- I. 斐波那契數(shù)列
一個函數(shù),輸入 n 斜筐,求斐波那契(Fibonacci)數(shù)列的第 n 項(即 F(N))冰啃。斐波那契數(shù)列的定義如下:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數(shù)列由 0 和 1 開始邓夕,之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出肋层。
答案需要取模 1e9+7(1000000007),如計算初始結果為:1000000008翎迁,請返回 1栋猖。
示例 1:
輸入:n = 2
輸出:1
示例 2:
輸入:n = 5
輸出:5
提示:
0 <= n <= 100
題解:
class Solution:
def fib(self, n: int) -> int:
n = n % 1000000007
a = 0
if n == 0:
return a
b = 1
if n == 1:
return b
sum = 0
for i in range(2, n+1):
sum = a + b
a = b
b =sum
return sum % 1000000007
70. 爬樓梯
新解法:爬樓梯到當前臺階只能從前一階臺階或前兩階臺階上來:F(n) = F(n - 1) + F(n - 2)
class Solution:
def climbStairs(self, n: int) -> int:
init0 = 1
init1 = 1
if n <= 1:
return 1
for i in range(n - 1):
ans = init1 + init0
init0 = init1
init1 = ans
return ans
746. 使用最小花費爬樓梯
題解:
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp1 = 0
dp2 = 0
for i in range(2, len(cost)+1):
dp = min(dp1 + cost[i-1], dp2 + cost[i-2])
dp2 = dp1
dp1 = dp
return dp1
53. 最大子數(shù)組和
給你一個整數(shù)數(shù)組 nums ,請你找出一個具有最大和的連續(xù)子數(shù)組(子數(shù)組最少包含一個元素)汪榔,返回其最大和蒲拉。
子數(shù)組 是數(shù)組中的一個連續(xù)部分。
示例 1:
輸入:nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出:6
解釋:連續(xù)子數(shù)組 [4,-1,2,1] 的和最大痴腌,為 6 雌团。
示例 2:
輸入:nums = [1]
輸出:1
示例 3:
輸入:nums = [5,4,-1,7,8]
輸出:23
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
分析:
- 狀態(tài):dp[i] : 以第i個數(shù)結尾的子數(shù)組
- 狀態(tài)轉移:
- 第i-1個數(shù)結尾的子數(shù)組加上第i個數(shù)
- 第i個數(shù)單獨作為子數(shù)組
- dp[i] = max{dp[i - 1] + num[i], num[i]}
- 初始狀態(tài)dp[0] = num[0]
- 最后執(zhí)行狀態(tài),再所有狀態(tài)中取dp最大的狀態(tài)作為結果返回
題解:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
l = len(nums)
dp = [0] * l
dp[0] = nums[0]
for i in range(1, l):
dp[i] = max(dp[i-1] + nums[i], nums[i])
return max(dp)
優(yōu)化空間:在上述的狀態(tài)轉移中士聪,我們需要一個和原始數(shù)組一樣大的數(shù)組存儲狀態(tài)锦援,但最終我們只需要這些狀態(tài)中的最大值,既然只需要最大值剥悟,那我我們只需要一個空間存最大值灵寺,一個空間取遍歷就好了
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = nums[0]
sum = nums[0]
for i in range(1, len(nums)):
sum = max(sum + nums[i], nums[i])
if sum > ans:
ans = sum
return ans
198. 打家劫舍
你是一個專業(yè)的小偷,計劃偷竊沿街的房屋区岗。每間房內都藏有一定的現(xiàn)金略板,影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng),如果兩間相鄰的房屋在同一晚上被小偷闖入慈缔,系統(tǒng)會自動報警叮称。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組,計算你 不觸動警報裝置的情況下 藐鹤,一夜之內能夠偷竊到的最高金額瓤檐。
示例 1:
輸入:[1,2,3,1]
輸出:4
解釋:偷竊 1 號房屋 (金額 = 1) ,然后偷竊 3 號房屋 (金額 = 3)娱节。
偷竊到的最高金額 = 1 + 3 = 4 挠蛉。
示例 2:
輸入:[2,7,9,3,1]
輸出:12
解釋:偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9),接著偷竊 5 號房屋 (金額 = 1)括堤。
偷竊到的最高金額 = 2 + 9 + 1 = 12 碌秸。
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 400
分析:
- 確定狀態(tài):dp[i]:判斷偷第i家的狀態(tài)
- 狀態(tài)轉移:
- 對于dp[i]這個狀態(tài)绍移,要么偷了第i家悄窃,收益是nums[i] + dp[i-2]
- 要么沒有偷第i家,收益是偷上一家的dp[i-1]
- dp[i] = max(nums[i] + dp[i-2], dp[i-1])
- 初始狀態(tài):
- 只有一家:dp[0] = nums[0]蹂窖,即這家收益
- 只有兩家:dp[1] = max(nums[0], nums[1])轧抗,即偷收益多的那家
- 執(zhí)行狀態(tài),最后一次偷的即最高金額
題解:
class Solution:
def rob(self, nums: List[int]) -> int:
l = len(nums)
if l <= 2:
return max(nums)
dp = [0] * l
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, l):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
空間優(yōu)化:與上一題類似瞬测,對于求最大部分横媚。如果用的是數(shù)組可以用兩個變量優(yōu)化空間
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: return 0
dp = [0]*n
dp2 = 0
dp1 = 0
for i in range(0, n):
dp = max(dp2 + nums[i], dp1)
dp2 = dp1
dp1 = dp;
return dp1
總結:對于出現(xiàn)求最大值需要對此敏感纠炮,如果最大值針對一個數(shù)組狀態(tài),便可以考慮優(yōu)化為兩個變量代替灯蝴,讓空間復雜度由O(n)->O(1)
740. 刪除并獲得點數(shù)
給你一個整數(shù)數(shù)組 nums 恢口,你可以對它進行一些操作。
每次操作中穷躁,選擇任意一個 nums[i] 耕肩,刪除它并獲得 nums[i] 的點數(shù)。之后问潭,你必須刪除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素猿诸。
開始你擁有 0 個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)狡忙。
示例 1:
輸入:nums = [3,4,2]
輸出:6
解釋:
刪除 4 獲得 4 個點數(shù)梳虽,因此 3 也被刪除。
之后灾茁,刪除 2 獲得 2 個點數(shù)窜觉。總共獲得 6 個點數(shù)北专。
示例 2:
輸入:nums = [2,2,3,3,3,4]
輸出:9
解釋:
刪除 3 獲得 3 個點數(shù)竖螃,接著要刪除兩個 2 和 4 。
之后逗余,再次刪除 3 獲得 3 個點數(shù)特咆,再次刪除 3 獲得 3 個點數(shù)。
總共獲得 9 個點數(shù)录粱。
提示:
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
分析:轉化為打家劫舍問題腻格,只不過這次不是根據數(shù)組下標決定狀態(tài)數(shù),而是根據數(shù)組中可能取到的最大值作為狀態(tài)數(shù)目啥繁。
題解:
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
cnt = [0] * 10001
for n in nums:
cnt[n] += 1
dp1 = 0
dp2 = 0
for i in range(0, len(cnt)):
dp = max(dp2 + i * cnt[i], dp1)
dp2 = dp1
dp1 = dp
return dp1
121. 買賣股票的最佳時機
題解:
方法一:轉化為求最大連續(xù)字串和問題
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l = len(prices)
new = [0] * l
for i in range(1, l):
new[i] = prices[i] - prices[i-1]
init = new[0]
ans = 0
for i in range(1, l):
init = max(init + new[i], new[i])
ans = max(ans, init)
return ans
方法二:前綴最值角度
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l = len(prices)
prev_min = [0] * l
prev_min[0] = prices[0]
ans = 0
for i in range(1, l):
prev_min[i] = min(prev_min[i-1], prices[i])
ans = max(ans, prices[i] - prev_min[i])
return ans
1014. 最佳觀光組合
給你一個正整數(shù)數(shù)組 values菜职,其中 values[i] 表示第 i 個觀光景點的評分,并且兩個景點 i 和 j 之間的 距離 為 j - i旗闽。
一對景點(i < j)組成的觀光組合的得分為 values[i] + values[j] + i - j 酬核,也就是景點的評分之和 減去 它們兩者之間的距離。
返回一對觀光景點能取得的最高分适室。
示例 1:
輸入:values = [8,1,5,2,6]
輸出:11
解釋:i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2:
輸入:values = [1,2]
輸出:2
提示:
2 <= values.length <= 5 * 104
1 <= values[i] <= 1000
題解:
方法一:將最優(yōu)化目標拆成i和j的部分嫡意,再一次循環(huán)中j部分是固定的,我們只需要j前value[i] + i的最大項提前存起來即可捣辆。注意這里不能循環(huán)求解value[i] + i蔬螟,否則就是暴力窮舉了,時間復雜度不滿足要求
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
l = len(values)
maxnum = 0
left = values[0]
for i in range(1, l):
maxnum = max(values[i] - i + left, maxnum)
left = max(values[i] + i, left)
return maxnum
方法二: 狀態(tài)轉移:假設我們已知前一個節(jié)點 j 能組成的最大的組合為(i汽畴,j)旧巾, 那么緊接著的一個節(jié)點 j+1 最大得分的組合一定是(i耸序,j+1)和(j,j+1)這兩個組合中較大的一個鲁猩。
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
l = len(values)
dp = [0] * l
dp[0] = values[0]
dp[1] = values[1] + values[0] - 1
for i in range(2, l):
dp[i] = max(values[i] + values[i-1] - 1, dp[i-1] + values[i] - values[i-1] - 1)
return max(dp)
注意:對于抽象的問題要善于總結當前狀態(tài)與上一個狀態(tài)的聯(lián)系
1299. 將每個元素替換為右側最大元素
給你一個數(shù)組 arr 坎怪,請你將每個元素用它右邊最大的元素替換,如果是最后一個元素廓握,用 -1 替換芋忿。
完成所有替換操作后,請你返回這個數(shù)組疾棵。
示例 1:
輸入:arr = [17,18,5,4,6,1]
輸出:[18,6,6,6,1,-1]
解釋:
- 下標 0 的元素 --> 右側最大元素是下標 1 的元素 (18)
- 下標 1 的元素 --> 右側最大元素是下標 4 的元素 (6)
- 下標 2 的元素 --> 右側最大元素是下標 4 的元素 (6)
- 下標 3 的元素 --> 右側最大元素是下標 4 的元素 (6)
- 下標 4 的元素 --> 右側最大元素是下標 5 的元素 (1)
- 下標 5 的元素 --> 右側沒有其他元素戈钢,替換為 -1
示例 2:
輸入:arr = [400]
輸出:[-1]
解釋:下標 0 的元素右側沒有其他元素。
提示:
1 <= arr.length <= 104
1 <= arr[i] <= 105
題解:后綴最值問題
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
l = len(arr)
if l <= 1:
return [-1]
dp = [0] * l
dp[-1] = -1
for i in range(l-2, -1, -1):
dp[i] = max(dp[i+1], arr[i+1])
return dp