人與狗做的網(wǎng)站手機(jī)怎么建立網(wǎng)站
文章目錄
- 題目
- 思路
- 代碼
- 動(dòng)態(tài)規(guī)劃簡(jiǎn)介
- **一、什么是動(dòng)態(tài)規(guī)劃**
- **二、動(dòng)態(tài)規(guī)劃的應(yīng)用場(chǎng)景**
- **三、動(dòng)態(tài)規(guī)劃的基本步驟**
- **四、動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn)**
題目
題目鏈接: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ī)劃:
- 狀態(tài)表示:
dp[i]:到達(dá)i位置所用最小花費(fèi) - 狀態(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)用,例如:
- 求解最短路問(wèn)題,如在圖中找到從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的最短路徑。
- 例如,在一個(gè)城市交通網(wǎng)絡(luò)中,尋找從起點(diǎn)到終點(diǎn)的最短行駛路線。
- 資源分配問(wèn)題,如何合理分配有限的資源以達(dá)到最優(yōu)效果。
- 比如在項(xiàng)目管理中,合理分配人力和時(shí)間資源,以使項(xiàng)目能夠在最短時(shí)間內(nèi)完成。
- 背包問(wèn)題,給定一組物品和一個(gè)背包容量,選擇哪些物品放入背包能使價(jià)值最大化。
三、動(dòng)態(tài)規(guī)劃的基本步驟
- 定義狀態(tài)表示:明確問(wèn)題中的狀態(tài)變量,這些變量通常用來(lái)描述子問(wèn)題的解。
- 建立狀態(tài)轉(zhuǎn)移方程:找出不同狀態(tài)之間的關(guān)系,確定如何從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)。
- 初始化邊界條件:確定初始狀態(tài)的值。
- 按照合適的順序計(jì)算狀態(tài)值:通常是從邊界條件開(kāi)始,逐步計(jì)算其他狀態(tài)的值。
四、動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn)
優(yōu)點(diǎn):
- 能夠有效地降低算法的時(shí)間復(fù)雜度,避免重復(fù)計(jì)算。
- 對(duì)于具有最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題的問(wèn)題,能夠得到最優(yōu)解。
缺點(diǎn):
- 空間復(fù)雜度可能較高,需要存儲(chǔ)狀態(tài)值。
- 狀態(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ì)有效的算法。