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

欧阳大哥2013

发布于 2022-01-20 12:30:59

5150

发布于 2022-01-20 12:30:59

文章被收录于专栏：欧阳大哥的轮子欧阳大哥的轮子

很多算法或者面试题中都会涉及到：动态规划 的问题。动态规划从数学的角度来看，就是存在一个有

个元素的集合

。这个集合可以构建出

种组合的集类:

问题的解决就是要找出满足条件的子集

来。反过来说，我们可以遍历集类中的每个子集，然后判断这个子集是否满足问题条件，如果满足则对子集进行处理，最后再得出最优解。这种方法的时间复杂度为

，虽然不是最佳解决方案确是最通用的暴力解决方案。

按照上述规则实现通用解法可以按如下步骤(本文用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;
    });

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022.01.04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度