公共模版

int maxv=-INF；
//最優(yōu)值設(shè)為全局變量
inline void DFS(int i,int x1,...,int xn)
//i用來(lái)控制層數(shù)，作為邊界條件的判斷依據(jù)，x1...xn是最優(yōu)化變量或與其相關(guān)的量
{
        .......
}

括號(hào)里面的內(nèi)容視以下三種而定，最后會(huì)給出總結(jié)

1. 每一層必須選一個(gè)

思路：先加上當(dāng)前的值，然后邊界判斷，如果滿足最優(yōu)，更新最優(yōu)值，返回程序，執(zhí)行該步驟的下一個(gè)狀態(tài)，比如在例題中可以選擇(x+1,y)和(x+1,y+1)就執(zhí)行下一個(gè)狀態(tài)的dfs，之后恢復(fù)原來(lái)的變量值（恢復(fù)到未選擇之前的狀態(tài)，因?yàn)檫€有其他的下一個(gè)狀態(tài)要跑）
例題：
從頂層開(kāi)始向下走，每走下一級(jí)，可向左下方向或右下方向走。求走到底層后它所經(jīng)過(guò)數(shù)字的總和的最大值。
【輸入格式】
第一個(gè)整數(shù)為n,一下n行為各層的數(shù)字。
【輸出格式】
一個(gè)整數(shù)，即最大值。
【輸入樣例 】
5
1
6 3
8 2 6
2 1 6 5
3 2 4 7 6
【輸出樣例】
23
【樣例說(shuō)明】
最大值=1+3+6+6+7=23

void dfs(int i,int j){
    sum+=a[i][j];
    if(i==N)
    {
        if(sum>Max)
        Max=sum;
        return ;
    }
    for(int x=0;x<2;x++){
        dfs(i+1,j+x);
        sum-=a[i+1][j+x];    
}  

2. 任何一步都可選可不選

分析：這一步其實(shí)是上一步的變種，變化在于首先不能從第一步開(kāi)始，因?yàn)榈谝徊绞强梢圆贿x的，其次因?yàn)槊恳徊蕉际强蛇x可不選的，其實(shí)可以看成每一個(gè)的下一步都有兩種狀態(tài)可以轉(zhuǎn)移，一個(gè)是選擇了這種狀態(tài)的，一個(gè)是沒(méi)選的
思路：先進(jìn)行邊界判斷，若比最優(yōu)值還優(yōu)則更新，返回。
dfs(i+1,x1);
dfs(i+1,x1+a
例題：
洛谷P2036(洛谷P2677也很經(jīng)典)

#define N 2000000000
using namespace std;
int minv=N;
int n;
vector<int> acid,sweet;
void dfs(int i,int sum,int mult,int sub)
{
    if(i==n)
    {
        if(sub<minv)
            minv=sub;
        return;
    }
    dfs(i+1,sum+sweet[i+1],mult*acid[i+1],abs(sum+sweet[i+1]-mult*acid[i+1]));
    dfs(i+1,sum,mult,sub);
}
int main()
{
    cin>>n;
    acid.resize(n+1);
    sweet.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>acid[i]>>sweet[i];
    }
    dfs(0,0,1,N);
    cout<<minv<<endl;
    return 0;
}