动态规划

动态规划(dynamic programming)

动态规划与分治法(divide-and-conquer)相似,是一种将复杂问题分解成多个简单子问题,然后通过组合子问题的解来求解原问题。不同的是,动态规划会处理子问题重叠情况,也就是相同的子问题只会求解一次。

动态规划通常用来求解 最优化问题(optimization problem),这类问题可以有很多的解,我们找的是其中一个最优解(可能有很多最优解)

动态规划设计步骤:

1.刻画一个最优解结构特征

2.递归定义最优解的值

3.计算最优解的值,通常采用自底向上法

4.利用计算出的信息构造一个最优解


什么时候应该用动态规划:

当一个问题具有 最优子结构(Optimal Substructure) 和 重叠子问题(Overlapping Subproblems)性质时

适用情况:

1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为是否采用动态规划算法解决问题提供了重要线索

2.无后效性。即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响

3.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。


重叠子问题例子

比如求解 斐波那契 数列

                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

函数实现如下

int fib(int n) 
{ 
   if ( n <= 1 ) 
      return n; 
   return fib(n-1) + fib(n-2); 
}

求解 fib(3) 求解了2次,fib(2) 求解了3次,fib(1) 求解了5次,fib(0)求解了3次

自顶向下记忆法(Memoization)

#include <stdio.h>

int lookup[15];

int fib(int n)
{
    if (lookup[n] != -1)
        return lookup[n];

    if (n <= 1)
        lookup[n] = n;
    else
        lookup[n] = fib(n-1) + fib(n-2);

    return lookup[n];
}

int main()
{
    int i;
    for (i = 0; i < 15; i++)
        lookup[i] = -1;
    printf("fib(10) = %d\n", fib(10));
}

自底向上表格法(Tabulation)

#include <stdio.h>

int fib(int n) 
{ 
  int f[n+1]; 
  int i; 
  f[0] = 0;   f[1] = 1;  
  for (i = 2; i <= n; i++) 
      f[i] = f[i-1] + f[i-2]; 
  
  return f[n]; 
} 

int main()
{
    printf("fib(10) = %d\n", fib(10));
}

这两种解法都保留了子问题解


最优子结构

比如最短路径问题就是根据最优子结构性质,比如 x 如果在最短路径 u -> v 中间,那么 u -> v 的最短路径是 u -> x 最短路径 和 x -> v 最短路径的组合。

即 u -> v 的最优解可以分解为两个子问题的最优解




上一篇: 排序算法(3)-特征记录
下一篇: 编辑距离
作者邮箱: 203328517@qq.com