動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃（英語(yǔ)：Dynamic programming，簡(jiǎn)稱(chēng)DP）是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方...
IP屬地：香港
-
快速入門(mén)動(dòng)態(tài)規(guī)劃（背包問(wèn)題、硬幣找零問(wèn)題、編輯距離問(wèn)題、最長(zhǎng)上升子序列問(wèn)題、最長(zhǎng)公共子序列問(wèn)題、旅行商問(wèn)題） -
算法設(shè)計(jì)與分析筆記之NP完備性理論一. P、NP、NPC ??三類(lèi)問(wèn)題都會(huì)涉及到多項(xiàng)式時(shí)間算法，我們先解決什么是多項(xiàng)式時(shí)間算法。??多項(xiàng)式時(shí)間的算法的形式化定義是，對(duì)于規(guī)模為n的輸入，在最壞情況下的運(yùn)行時(shí)間是...
-
算法設(shè)計(jì)與分析筆記之最大流/最小割問(wèn)題割（Cut） s-t cut：(A, B)，將圖分為兩部分A和B，源s∈A，終點(diǎn)t∈Bcut(A, B)的容量（capacity）：所有流出A的邊的容量和，注意區(qū)分與流量（f...
-
入門(mén)貪心算法貪心算法必知的知識(shí)點(diǎn) 貪心算法（又稱(chēng)貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。 ...
-
最長(zhǎng)公共子序列（LCS）——?jiǎng)討B(tài)規(guī)劃問(wèn)題描述 ??子序列是指，從序列中選出一些子元素，需滿(mǎn)足其前后關(guān)系與在原序列中相同；公共是指該序列同時(shí)是兩個(gè)序列的子序列。如兩個(gè)序列{4，2，1 ，6，5，8，13，18，9...
-
硬幣找零問(wèn)題——?jiǎng)討B(tài)規(guī)劃
問(wèn)題闡述 給定一些面值的硬幣（數(shù)量不限）和需要找零的金額，求一個(gè)找零所需硬幣數(shù)最少的方案?，F(xiàn)實(shí)生活中因其面值的特殊性，我們往往采用貪心策略，即每次選取滿(mǎn)足條件的面值最大的硬幣...
-
背包問(wèn)題之0-1背包
背包問(wèn)題是典型的動(dòng)態(tài)規(guī)劃例子。我們可將子問(wèn)題的解存儲(chǔ)下來(lái)，以免計(jì)算其母問(wèn)題時(shí)需用到子問(wèn)題結(jié)果而重復(fù)計(jì)算。 問(wèn)題闡述 給定背包容量W，n個(gè)物品及各個(gè)物品的價(jià)值和重量，問(wèn)如何選擇...
-
不帶權(quán)重的區(qū)間調(diào)度問(wèn)題——?jiǎng)討B(tài)規(guī)劃、貪心算法問(wèn)題闡述 已知若干個(gè)工作的開(kāi)始時(shí)間和結(jié)束時(shí)間，求最大兼容的活動(dòng)個(gè)數(shù)。舉例，如下四個(gè)活動(dòng)活 動(dòng)i 1 2 3...
