很多算法或者面試題中都會(huì)涉及到：動(dòng)態(tài)規(guī)劃 的問題。 動(dòng)態(tài)規(guī)劃從數(shù)學(xué)的角度來看，就是存在一個(gè)有個(gè)元素的集合。這個(gè)集合可以構(gòu)建出種組合的集類:

問題的解決就是要找出滿足條件的子集來。 反過來說，我們可以遍歷集類中的每個(gè)子集，然后判斷這個(gè)子集是否滿足問題條件，如果滿足則對(duì)子集進(jìn)行處理，最后再得出最優(yōu)解。這種方法的時(shí)間復(fù)雜度為，雖然不是最佳解決方案確是最通用的暴力解決方案。

按照上述規(guī)則實(shí)現(xiàn)通用解法可以按如下步驟(本文用OC語言實(shí)現(xiàn)，其他語言可參考)：

1. 遍歷集類中的所有子集

可以通過遞歸的方法來實(shí)現(xiàn)子集的遍歷，代碼如下：

/**
  array:指定要處理的集合
  start:最開始取元素的位置
  subArray: 保存遍歷得到的子集。
*/
void dynamicProgram(NSArray *array, NSInteger start, NSMutableArray *subArray) {
    
    //遞歸調(diào)用分別生成集類中的子集。
    NSInteger count = array.count;
    for (NSInteger i = start; i < count; i++) {
        [subArray addObject:array[i]];
        
        //這里的subArray就是集類中的一個(gè)子集。
        
        //進(jìn)行遞歸調(diào)用
        dynamicProgram(array, i + 1, subArray);
        [subArray removeLastObject];
    }
    
    //調(diào)用的方法的示例如下：
    dynamicProgram(@[@1,@2,@3,@4], 0, [@[] mutableCopy]);

2. 對(duì)每個(gè)子集進(jìn)行條件判斷和處理

上述的代碼中生成了一個(gè)通用的遍歷子集的方法。為了讓代碼更加通用，我們可以分別加入一個(gè)條件過濾器和處理器來讓調(diào)用者做自定義處理，同時(shí)為了保存每次處理的結(jié)果我們可以加入一個(gè)自定義上下文信息來保存擴(kuò)展參數(shù)。因此上述的代碼改進(jìn)如下：

//輔助函數(shù)。
static void dynamicProgramHelper(NSArray *array, void *ctx, NSInteger start, NSMutableArray *subArray, NSInteger * subIndexs, BOOL(^filter)(NSArray *subArray, NSInteger *subIndexs, void *ctx), BOOL(^handler)(NSArray *subArray, void* ctx) ) {
    
    //遞歸調(diào)用分別生成集類中的子集。
    NSInteger count = array.count;
    NSInteger subCount = subArray.count;
    for (NSInteger i = start; i < count; i++) {
        //保存子集中元素在集合中的索引。
        subIndexs[subCount] = i;
        [subArray addObject:array[i]];
        if (filter(subArray, subIndexs, ctx)) {
            if (!handler(subArray,ctx)) {
                break;
            }
        }
        dynamicProgramHelper(array, ctx, i + 1, subArray, subIndexs, filter, handler);
        [subArray removeLastObject];
    }
}

/**
 array:指定要處理的集合
 ctx: 保存上下文信息
 filter: 指定條件過濾器，入?yún)椋鹤蛹⒆蛹卦谌械乃饕龜?shù)組、上下文。 如果滿足條件則返回true表明會(huì)進(jìn)行計(jì)算處理，否則返回false.
 handler: 指定處理器，入?yún)椋鹤蛹?、上下文。如果已?jīng)得到最佳結(jié)果則返回false表明終止處理，否則返回true繼續(xù)處理。
 */
void dynamicProgram(NSArray *array, void *ctx, BOOL(^filter)(NSArray *subArray, NSInteger *subIndexs, void *ctx), BOOL(^handler)(NSArray *subArray, void *ctx) ) {
    
    NSMutableArray *subArray = [NSMutableArray new];
    NSInteger *subIndexs = malloc(sizeof(NSInteger)*array.count);
    dynamicProgramHelper(array, ctx, 0, subArray, subIndexs, filter, handler);
    free(subIndexs);
}

上面的通用算法中我們將動(dòng)態(tài)規(guī)劃的處理分解為了條件和計(jì)算，條件是用來判斷是否滿足計(jì)算的要求，計(jì)算則對(duì)滿足條件的每個(gè)子集進(jìn)行計(jì)算。所以如果能將所有問題都分為條件和計(jì)算的話那么問題就好解決了。接下來我們將用上面的動(dòng)態(tài)規(guī)劃通用算法來解決幾個(gè)經(jīng)典的問題：

1.小偷問題

分析這個(gè)問題可以看出：條件是房子不能相鄰，也就是索引值不能相差1。計(jì)算是求最大的金額。因此實(shí)現(xiàn)代碼如下：

//保存最大的金額，作為上下文參數(shù)。
NSInteger maxSum = 0;
dynamicProgram(@[@2,@7,@9,@3,@1], &maxSum, ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
        
        //條件是：房子不能相鄰，因此判斷的方法就是子數(shù)組的索引是不能相連的。
        //算法是：如果兩個(gè)索引之間相差1則表明不滿足條件。
       NSInteger index = subIndexs[0];
        for (NSInteger i = 1; i < subArray.count; i++) {
            if (index == subIndexs[i] - 1) {
                return NO;
            }
            index = subIndexs[i];
        }
        return YES;
        
    }, ^BOOL(NSArray *subArray, void *ctx) {
        
        //計(jì)算當(dāng)前子集的金額之和
        NSInteger sum = 0;
        for (NSNumber *num in subArray) {
            sum += num.integerValue;
        }
        //判斷是否是最大，如果不是則修改最大值
        NSInteger *pmaxSum = (NSInteger*)ctx;
        if (sum > *pmaxSum) {
            *pmaxSum = sum;
        }
        return YES;
    });
    
    NSLog(@"偷到的最大的金額是:%ld",maxSum);

2.最大子序列和

分析這個(gè)問題可以看出：條件是位置要相鄰,也就是說索引值之間必須相差1。計(jì)算是求最大的值?？梢钥闯鲞@個(gè)問題就是上面小偷問題具有相反條件，相同的計(jì)算。因此實(shí)現(xiàn)代碼如下：

NSInteger maxSum = 0;
dynamicProgram(@[@-2,@1,@-3,@4,@-1,@2,@1,@-5,@4], &maxSum, ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
        
        //條件是：位置必須相鄰，因此判斷的方法就是子數(shù)組的索引是相鄰的。
        //算法是：如果兩個(gè)索引之間不相差1則表明不滿足條件。
       NSInteger index = subIndexs[0];
        for (NSInteger i = 1; i < subArray.count; i++) {
            if (index != subIndexs[i] - 1) {
                return NO;
            }
            index = subIndexs[i];
        }
        return YES;
        
    }, ^BOOL(NSArray *subArray, void *ctx) {
        
        //計(jì)算當(dāng)前子集的之和
        NSInteger sum = 0;
        for (NSNumber *num in subArray) {
            sum += num.integerValue;
        }
        //判斷是否是最大，如果不是則修改最大值
        NSInteger *pmaxSum = (NSInteger*)ctx;
        if (sum > *pmaxSum) {
            *pmaxSum = sum;
        }
        
        return YES;
        
    });
    
    NSLog(@"最大子序列之和:%ld",maxSum);
    

3.硬幣組合問題

這個(gè)問題中如果硬幣的類型是1，2，5，然后總額是11元。所以組成的數(shù)組應(yīng)該是:[1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,5,5]。 條件就變?yōu)樽蛹慕痤~數(shù)量加起來必須是等于11。計(jì)算的就是得到最小數(shù)量的子集。所以代碼如下：

NSArray *coins = @[@1,@1,@1,@1,@1,@1,@1,@1,@1,@1,@1,@2,@2,@2,@2,@2,@5,@5];
    //開始時(shí)最小的數(shù)量為全集。
    NSMutableArray *minCoins = [coins mutableCopy];
    
    dynamicProgram(coins, (__bridge void *)(minCoins), ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
        
        //條件是元素的和必須要等于11元。
        NSInteger sum = 0;
        for (NSNumber *num in subArray) {
            sum += num.integerValue;
        }
        return sum == 11;
        
    }, ^BOOL(NSArray *subArray, void *ctx) {
        
        //比較數(shù)量，取最小數(shù)量的。
        NSMutableArray *minCoins = (__bridge NSMutableArray *)(ctx);
        if (minCoins.count > subArray.count) {
            [minCoins setArray:subArray];
        }
        
        return YES;
    });