许多算法或者面试题中都会涉及到：动态规划 的问题。 动态规划从数学的角度来看，便是存在一个有nn个元素的调集AA。这个调集能够构建出2n−12^n-1种组合的集类:

P(A)=⎨Si∣Si⊆A⎬i=1…2n−1P(A)= ⎨Si|Si⊆A⎬ i=1…2^n-1

问题的处理便是要找出满意条件的子集SiSi来。 反过来说，咱们能够遍历集类中的每个子集，然后判别这个子集是否满意问题条件，假如满意则对子集进行处理，最终再得出最优解。这种方法的时间复杂度为O(2n)O(2^n)，虽然不是最佳处理方案确是最通用的暴力处理方案。

按照上述规则完成通用解法能够按如下过程(本文用OC言语完成，其他言语可参考)：

1. 遍历集类中的一切子集

能够通过递归的方法来完成子集的遍历，代码如下：

/**
  array:指定要处理的调集
  start:最开端取元素的位置
  subArray: 保存遍历得到的子集。
*/
void dynamicProgram(NSArray *array, NSInteger start, NSMutableArray *subArray) {
    //递归调用别离生成集类中的子集。
    NSInteger count = array.count;
    for (NSInteger i = start; i < count; i++) {
        [subArray addObject:array[i]];
        //这儿的subArray便是集类中的一个子集。
        //进行递归调用
        dynamicProgram(array, i + 1, subArray);
        [subArray removeLastObject];
    }
    //调用的方法的示例如下：
    dynamicProgram(@[@1,@2,@3,@4], 0, [@[] mutableCopy]);

2. 对每个子集进行条件判别和处理

上述的代码中生成了一个通用的遍历子集的方法。为了让代码愈加通用，咱们能够别离参加一个条件过滤器和处理器来让调用者做自定义处理，一起为了保存每次处理的成果咱们能够参加一个自定义上下文信息来保存扩展参数。因而上述的代码改进如下：


//辅助函数。
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) ) {
    //递归调用别离生成集类中的子集。
    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: 指定条件过滤器，入参为：子集、子集元素在全集中的索引数组、上下文。 假如满意条件则回来true标明会进行核算处理，否则回来false.
 handler: 指定处理器，入参为：子集、上下文。假如已经得到最佳成果则回来false标明终止处理，否则回来true继续处理。
 */
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);
}

上面的通用算法中咱们将动态规划的处理分化为了条件和核算，条件是用来判别是否满意核算的要求，核算则对满意条件的每个子集进行核算。所以假如能将一切问题都分为条件和核算的话那么问题就好处理了。接下来咱们将用上面的动态规划通用算法来处理几个经典的问题：

1.小偷问题

动态规划的数学本质以及通用解法

剖析这个问题能够看出：条件是房子不能相邻，也便是索引值不能相差1。核算是求最大的金额。因而完成代码如下：

//保存最大的金额，作为上下文参数。
NSInteger maxSum = 0;
dynamicProgram(@[@2,@7,@9,@3,@1], &maxSum, ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
        //条件是：房子不能相邻，因而判别的方法便是子数组的索引是不能相连的。
        //算法是：假如两个索引之间相差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) {
        //核算当时子集的金额之和
        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.最大子序列和

动态规划的数学本质以及通用解法

剖析这个问题能够看出：条件是位置要相邻,也便是说索引值之间有必要相差1。核算是求最大的值。能够看出这个问题便是上面小偷问题具有相反条件，相同的核算。因而完成代码如下：


NSInteger maxSum = 0;
dynamicProgram(@[@-2,@1,@-3,@4,@-1,@2,@1,@-5,@4], &maxSum, ^BOOL(NSArray *subArray, NSInteger *subIndexs, void *ctx) {
        //条件是：位置有必要相邻，因而判别的方法便是子数组的索引是相邻的。
        //算法是：假如两个索引之间不相差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) {
        //核算当时子集的之和
        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.硬币组合问题

动态规划的数学本质以及通用解法

这个问题中假如硬币的类型是1，2，5，然后总额是11元。所以组成的数组应该是:[1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,5,5]。 条件就变为子集的金额数量加起来有必要是等于11。核算的便是得到最小数量的子集。所以代码如下：


NSArray *coins = @[@1,@1,@1,@1,@1,@1,@1,@1,@1,@1,@1,@2,@2,@2,@2,@2,@5,@5];
    //开端时最小的数量为全集。
    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) {
        //比较数量，取最小数量的。
        NSMutableArray *minCoins = (__bridge NSMutableArray *)(ctx);
        if (minCoins.count > subArray.count) {
            [minCoins setArray:subArray];
        }
        return YES;
    });