題目

題目鏈接：https://www.nowcoder.com/practice/9b969a3ec20149e3b870b256ad40844e?tpld=230&tpld=39751&ru=/exam/oj

思路

有幾個(gè)細(xì)節(jié)要明確

• const[i]是在離開(kāi)時(shí)花費(fèi)的體力所以在離開(kāi)時(shí)才會(huì)加
• 根據(jù)例子我們能知道數(shù)組給了i個(gè)數(shù)我們下標(biāo)到達(dá)i才算到頂，如圖如果我們必須到達(dá)cost[i+1]才算登頂

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

1. 狀態(tài)表示：
   dp[i]：到達(dá)i位置所用最小花費(fèi)
2. 狀態(tài)轉(zhuǎn)移方程
   
   因?yàn)橐淮沃荒芟蛏弦粋€(gè)臺(tái)階或者兩個(gè)臺(tái)階所以只有i-1,i-2兩種可能。

	dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

代碼

#include <iostream>
using namespace std;#define N 100010int main() {int cost[N]={0};int dp[N]={0};int n;cin >> n;for(int i=0;i<n;i++)cin >> cost[i];for(int i=2;i<=n;i++)dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);cout << dp[n] << endl;return 0;
}

動(dòng)態(tài)規(guī)劃簡(jiǎn)介

一、什么是動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃（Dynamic Programming）是一種在解決多階段決策問(wèn)題時(shí)常用的算法思想。它通過(guò)將復(fù)雜問(wèn)題分解成一系列相互關(guān)聯(lián)的子問(wèn)題，并按照一定的順序求解這些子問(wèn)題，從而避免了重復(fù)計(jì)算，提高了算法的效率。上面的題的思想就是動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃的核心思想是“最優(yōu)子結(jié)構(gòu)”和“重疊子問(wèn)題”。最優(yōu)子結(jié)構(gòu)意味著一個(gè)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解。重疊子問(wèn)題則是指在求解過(guò)程中，相同的子問(wèn)題會(huì)被多次計(jì)算。

二、動(dòng)態(tài)規(guī)劃的應(yīng)用場(chǎng)景

動(dòng)態(tài)規(guī)劃在許多領(lǐng)域都有廣泛的應(yīng)用，例如：

1. 求解最短路問(wèn)題，如在圖中找到從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的最短路徑。
   • 例如，在一個(gè)城市交通網(wǎng)絡(luò)中，尋找從起點(diǎn)到終點(diǎn)的最短行駛路線。
2. 資源分配問(wèn)題，如何合理分配有限的資源以達(dá)到最優(yōu)效果。
   • 比如在項(xiàng)目管理中，合理分配人力和時(shí)間資源，以使項(xiàng)目能夠在最短時(shí)間內(nèi)完成。
3. 背包問(wèn)題，給定一組物品和一個(gè)背包容量，選擇哪些物品放入背包能使價(jià)值最大化。

三、動(dòng)態(tài)規(guī)劃的基本步驟

1. 定義狀態(tài)表示：明確問(wèn)題中的狀態(tài)變量，這些變量通常用來(lái)描述子問(wèn)題的解。
2. 建立狀態(tài)轉(zhuǎn)移方程：找出不同狀態(tài)之間的關(guān)系，確定如何從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)。
3. 初始化邊界條件：確定初始狀態(tài)的值。
4. 按照合適的順序計(jì)算狀態(tài)值：通常是從邊界條件開(kāi)始，逐步計(jì)算其他狀態(tài)的值。

四、動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 能夠有效地降低算法的時(shí)間復(fù)雜度，避免重復(fù)計(jì)算。
2. 對(duì)于具有最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題的問(wèn)題，能夠得到最優(yōu)解。

缺點(diǎn)：

1. 空間復(fù)雜度可能較高，需要存儲(chǔ)狀態(tài)值。
2. 狀態(tài)定義和轉(zhuǎn)移方程的推導(dǎo)可能比較困難，需要對(duì)問(wèn)題有深入的理解。

總之，動(dòng)態(tài)規(guī)劃是一種強(qiáng)大的算法思想，掌握它對(duì)于解決許多復(fù)雜的優(yōu)化問(wèn)題具有重要意義。但在實(shí)際應(yīng)用中，需要根據(jù)具體問(wèn)題的特點(diǎn)來(lái)選擇是否使用動(dòng)態(tài)規(guī)劃以及如何設(shè)計(jì)有效的算法。