1. 塔樹(shù)選擇和最大問(wèn)題
（見(jiàn)塔樹(shù)選擇和最大問(wèn)題)
一個(gè)高度為N的由正整數(shù)組成的三角形鸥跟，從上走到下，求經(jīng)過(guò)的數(shù)字和的最大值盔沫。每次只能走到下一層相鄰的數(shù)上医咨，例如從第3層的6向下走，只能走到第4層的2或9上架诞。
5
8 4
3 6 9
7 2 9 5
例子中的最優(yōu)方案是：5 + 8 + 6 + 9 = 28拟淮。
- 分析
直接分析，從上到下的考慮谴忧，發(fā)現(xiàn)無(wú)從下手好像只能遍歷很泊，但是反方向考慮則，則發(fā)現(xiàn)有趣的地方俏蛮，假設(shè)dp[i][j]為最下面一層到第i層j位置上的最大值撑蚌，考慮上圖6這個(gè)位置，那么其dp[3][2]應(yīng)該是什么呢搏屑？是下面相鄰的兩個(gè)位置的最大值+6,即dp[3][2] = max(dp[3+1][2],dp[3+1][2+1]) + a[3][2]争涌。
據(jù)此可以推導(dǎo)其公式為
dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + a[i][j]
根據(jù)上述公式編程思路如下
1、初始化最下面一排dp
2辣恋、由下往上亮垫，安裝上述公式對(duì)dp進(jìn)行賦值
3模软、dp[1][1]為最終所求
//最下面一層直接賦值
int rs = 0;
for (int i = 0; i<FLOOR; i++)
dp[FLOOR-1][i] = a[FLOOR-1][i];
//從倒數(shù)第二行起， 按照狀態(tài)轉(zhuǎn)移方程
//dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j]向上遞推
//直到dp[0][0]饮潦， 此時(shí)dp[0][0]就是結(jié)果
for (int i = FLOOR-2; i>=0; i--)
for (int j = 0; j<=i;j++)
dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
啟示：動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)燃异，經(jīng)常從后面往前考慮會(huì)瞬間明朗很多，塔數(shù)類問(wèn)題還有許多其他的變形參見(jiàn) 動(dòng)態(tài)規(guī)劃“數(shù)塔”類型題目總結(jié)
2. 乘法表問(wèn)題
定義于字母表∑(a,b,c)上的乘法表如表1所示
- 表1. ∑乘法表
∑ | a |b | c
:---:|:---:|:---:|:---:
a |b | b | a
b |c | b| a
c |a | c | c
依此乘法表,對(duì)任一定義于∑上的字符串,適當(dāng)加括號(hào)表達(dá)式后得到一個(gè)表達(dá)式继蜡。例如,對(duì)于字符串x=bbbba,它的一個(gè)加括號(hào)表達(dá)式為i(b(bb))(ba)回俐。依乘法表,該表達(dá)式的值為a。試設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法,對(duì)任一定義于∑上的字符串x=x1x2…xn稀并，計(jì)算有多少種不同的加括號(hào)方式,使由x導(dǎo)出的加括號(hào)表達(dá)式的值為a
要求：
輸入：輸入一個(gè)以a,b,c組成的任意一個(gè)字符串仅颇。
輸出：計(jì)算出的加括號(hào)方式數(shù)。
分析：
建立一個(gè)三位數(shù)組碘举，用于記錄一段連續(xù)的序列內(nèi)通過(guò)加括號(hào)可得到a忘瓦、b、c的方式數(shù)引颈，然后往長(zhǎng)度方向擴(kuò)展耕皮，因?yàn)槊績(jī)蓚€(gè)字母相乘的結(jié)果已給出，所以可通過(guò)加和乘運(yùn)算求出更大長(zhǎng)度的字符串得到a蝙场、b凌停、c的方式數(shù)具體算法：
數(shù)組維數(shù)為:p[n][n][3];
p[i][j][k] 表示 字符串xix(i+1)....xj的表達(dá)式的值為k(k>=0 k <=2,k=0表示a...) 的方式數(shù)；
遞推式為：
p[i][j][0]= sum(p[i][t][0]*p[t+1][j][2]+ p[i][t][1]*p[t+1][j][2]+p[i][t][2]*p[t+1][j][0])
p[i][j][1]與p[i][j][2]類似p[i][j][0] 的求法 t>=i 并且t <j
C++代碼：
#include <stdio.h>
#include <string.h>
int main() {
int n = 0;
char c;
int p[100][100][3] = {0};
while((c = getchar()) != '/n') {
p[n][n][c - 'a'] = 1;
n++;
}
for(int k = 1;k < n;k++) {
for(int i = 0;i < n-k;i++) {
int j = i + k;
for(int t = i;t < j;t++) {
p[i][j][0] += p[i][t][2]* p[t+1][j][0] + p[i][t][0]*p[t+1][j][2] + p[i][t][1]*p[t+1][j][2];
p[i][j][1] += p[i][t][0]*p[t+1][j][0] + p[i][t][0]*p[t+1][j][1] + p[i][t][1]*p[t+1][j][1];
p[i][j][2] += p[i][t][1]*p[t+1][j][0] + p[i][t][2]*p[t+1][j][1] + p[i][t][2]*p[t+1][j][2];
}
}
}
printf("%d/n",p[0][n-1][0]);
}
3. 爬樓梯
題目：
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
- 分析:
動(dòng)態(tài)規(guī)劃 d(i) = d(i-1) + d(i-2)
class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
dp = [0, 1, 2]
if n <= 2:
return dp[n]
dp += [0 for i in range (n-2)]
for i in range (3, n + 1):
dp[i] += dp[i-1] + dp[i-2]
return dp[n]
4. 最長(zhǎng)上升子序列（LIS）
問(wèn)題描述:
設(shè)L=<a1,a2,…,an>是n個(gè)不同的實(shí)數(shù)的序列李丰，L的遞增子序列是這樣一個(gè)子序列Lin=<aK1,ak2,…,akm>苦锨，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值趴泌。
- 分析：
這里采用的是逆向思維的方法，從最后一個(gè)開(kāi)始想起拉庶，即先從A[N]（A數(shù)組是存放數(shù)據(jù)的數(shù)組嗜憔，下同）開(kāi)始，則只有長(zhǎng)度為1的子序列氏仗，到A[N-1]時(shí)就有兩種情況吉捶，如果a[n-1] < a[n] 則存在長(zhǎng)度為2的不下降子序列 a[n-1],a[n]；如果a[n-1] > a[n] 則存在長(zhǎng)度為1的不下降子序列 a[n-1]或者a[n]皆尔。
有了以上的思想呐舔，DP方程就呼之欲出了（這里是順序推的，不是逆序的）：
DP[I]=MAX（1,DP[J]+1） J=0,1,...,I-1
但這樣的想法實(shí)現(xiàn)起來(lái)是）O(n^2)的慷蠕。本題還有更好的解法珊拼，就是O(n*logn)。利用了長(zhǎng)升子序列的性質(zhì)來(lái)優(yōu)化流炕，以下是優(yōu)化版的代碼：
//最長(zhǎng)不降子序
const int SIZE=500001;
int data[SIZE];
int dp[SIZE];
//返回值是最長(zhǎng)不降子序列的最大長(zhǎng)度,復(fù)雜度O(N*logN)
int LCS(int n) { //N是DATA數(shù)組的長(zhǎng)度,下標(biāo)從1開(kāi)始
int len(1),low,high,mid,i;
dp[1]=data[1];
for(i=1;i<=n;++i) {
low=1;
high=len;
while( low<=high ) { //二分
mid=(low+high)/2;
if( data[i]>dp[mid] ) {
low=mid+1;
}
else {
high=mid-1;
}
}
dp[low]=data[i];
if( low>len ) {
++len;
}
}
return len;
}
5. 背包問(wèn)題
有N件物品和一個(gè)容量為V的背包澎现。第i件物品的大小是c[i]仅胞，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大剑辫。
分析：
用DP[I][J] 表示前I件物品放入一個(gè)容量為J的背包可以獲得的最大價(jià)值干旧。則
DP[I][J]= DP[I-1][J] ,J<C[I]
MAX（DP[I-1][J]，DP[I-1][J-C[I]]+W[I]） , J>=C[I]
這樣實(shí)現(xiàn)的空間復(fù)雜度為O(VN)妹蔽，實(shí)際上可以優(yōu)化到O（V）椎眯。以下是代碼：
const int MAXW=13000; //最大重量
const int MAXN=3450; //最大物品數(shù)量
int c[MAXN]; //物品的存放要從下標(biāo)1開(kāi)始
int w[MAXN]; //物品的存放要從下標(biāo)1開(kāi)始
int dp[MAXW];
//不需要將背包裝滿，則將DP數(shù)組全部初始化為0
//要將背包裝滿胳岂，則初始化為DP[0]=0盅视，DP[1]…DP[V]=-1(即非法狀態(tài))
int Packet(int n,int v) {
int i,j;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;++i) {
for(j=v;j>=c[i];--j) { //這里是倒序，別弄錯(cuò)了
dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);
}
}
return dp[v];
}
6. 最長(zhǎng)公共子序列（LCS）
給出兩個(gè)字符串a(chǎn), b旦万，求它們的最長(zhǎng)闹击、連續(xù)的公共字串。
這很容易就想到以DP[I][J]表示A串匹配到I成艘，B串匹配到J時(shí)的最大長(zhǎng)度赏半。則：
0 I==0 || J==0
DP[I][J]= DP[I-1][J-1]+ 1 A[I]==B[J]
MAX（DP[I-1][J]，DP[I][J-1]） 不是以上情況
但這樣實(shí)現(xiàn)起來(lái)的空間復(fù)雜度為O(n^2)淆两，而上面的方程只與第I-1行有關(guān)断箫，所以可以用兩個(gè)一維數(shù)組來(lái)代替。以下是代碼：
//最長(zhǎng)公共子序列
const int SIZE=1001;
int dp[2][SIZE]; //兩個(gè)一維數(shù)組
//輸入兩個(gè)字符串秋冰，返回最大的長(zhǎng)度
int LCS(const string& a,const string& b) {
int i,j,flag;
memset(dp,0,sizeof(dp));
flag=1;
for(i=1;i<=a.size();++i) {
for(j=1;j<=b.size();++j) {
if( a[i-1]==b[j-1] ) dp[flag][j]=dp[1-flag][j-1]+1;
else dp[flag][j]=MAX(dp[flag][j-1],dp[1-flag][j]);
}
flag=1-flag;
}
return dp[1-flag][b.size()];
}
另見(jiàn) LCS
