特點(diǎn)：題目中直接包含坐標(biāo)的概念 State: f[x] 表示我從起點(diǎn)走到坐標(biāo)x f[x][y] 表示我從起點(diǎn)走到坐標(biāo) x, y Function...

特點(diǎn)：以字符串居多, f[i] 表示前i 個(gè)字符對(duì)于這個(gè)問題的答案 State： f[i] 表示前 i 個(gè)位置/數(shù)字/字符痛倚， 第 i 個(gè)... ...

特點(diǎn)：一般給兩個(gè)字符串 State: f[i][j] 代表了第一個(gè)sequence 的前i 個(gè)數(shù)字/字符蝠筑， 配上第二個(gè)sequence的前 j個(gè)...

題目：給一個(gè)序列研儒，求一次劃分區(qū)間程癌，求區(qū)間中的最大值 State: f[i]表示前 i 個(gè)元素的最大值 Function: f[i] = 前 i ...

特點(diǎn)： 用值作為DP 維度 （其他類型都是以位置坐標(biāo)做維度） DP過程就是填寫矩陣 可以滾動(dòng)數(shù)組優(yōu)化 背包： State:f[i][S] 前i ...

特點(diǎn)： 求一段區(qū)間的解max/min/count 轉(zhuǎn)移方程通過區(qū)間更新 從大到小的更新 這種問題的共性就是區(qū)間最后求[0,n-1]這樣一個(gè)區(qū)間逆...

博弈有先后手 State： 定義一個(gè)人的狀態(tài) Function: 考慮兩個(gè)人的狀態(tài)更新 Initialize Answer：先 考慮最小狀態(tài)然后...

本質(zhì)上：動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃就是解決了重復(fù)計(jì)算的搜索 大部分DP都可以用記憶化搜索做 動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)方式：循環(huán) （從小到大遞推）記憶化搜索（從大到...

什么情況下使用動(dòng)態(tài)規(guī)劃 滿足下面三個(gè)條件之一滋戳，則極有可能使用動(dòng)態(tài)規(guī)劃90%-95%： 求最大值猾担，最小值 判斷方案是否可行 統(tǒng)計(jì)方案個(gè)數(shù) 極不可能...