动态规划

动态规划(Dynamic Programming)，是求解决策过程(decision process)最优化的数学方法。

动态规划概述

通过把问题分解为相对简单的子问题的方式求解复杂问题，适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

采用动态规划求解的问题的一般要具有3个特点:

• 最优化原理：假设问题的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
• 无后效性：即某阶段状态一旦确定。就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响曾经的状态。仅仅与当前状态有关；
• 子问题的重叠性：一个子问题在下一阶段决策中可能被多次使用到（动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法）。

动态规划优化一般的优化流程：递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法。

递归的暴力解法

这个算法存在大量重复计算（重叠子问题），时间复杂度为 O(2^n)。

   // fibonacci
   static int fb1(int N) {
       if (N == 1 || N == 2)
           return 1;
       return fb1(N-1) + fb1(N-2);
   }

带备忘录的递归解法

带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数，时间复杂度为 O(n)，效率接近动态规划。

// fibonacci
long fb(long N) {
    vector<long> f(N+1, 0);
    f[1] = f[2] = 1;
    return helper(f, N);
} 

long helper(vector<long>& f, long n) {
    if (n > 0 && f[n] == 0)
        f[n] = helper(f, n-1) + helper(f, n-2);
    return f[n];
}

以上两种解法，只处理了非零参数情况。执行时间如下：

time ./test_fb1 n=45
1134903170 
real    0m17.511s
user    0m17.076s
sys     0m0.117s

time ./test_fb2 n=45
1134903170
real    0m0.005s
user    0m0.000s
sys     0m0.005s

time ./test_fb2 n=66
27777890035288
real    0m0.002s
user    0m0.002s
sys     0m0.000s

动态规划解法

状态转移方程

状态转移方程，是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第 K 阶段的状态 Sk 以及决策 uk(Sk)，则第 K+1 阶段的状态 Sk+1 也就完全确定。即有 S[k+1]= Tk(Sk, uk)

如：Fibonacci 的状态 n 是由状态 n-1 和状态 n-2 相加转移而来。

// fibonacci
long fb(long N) {
    vector<long> f(N+1, 0);
    f[1] = f[2] = 1;
    for (long i=3; i<=N; i++)
        f[i] = f[i-1] + f[i-2];
    return f[N];
}

根据 Fibonacci 数列的状态转移方程，当前状态只和之前的两个状态有关，因此可以只存储之前的两个状态，空间复杂度降为 O(1)。

long fb(long n) {
    if (n < 1) return -1;
    if (n < 3) return 1;
    long n1 = 1, n2 = 1, sum;
    for (long i=3; i<=n; i++) {
        sum = n1 + n2;
        n2 = n1;
        n1 = sum;
    }
    return sum;
}

最优子结构

　　原问题的解由子问题的最优解构成。要符合「最优子结构」，子问题间必须互相独立。 如：Coin Change问题中：

• 当 coin=5 时，dp[6] = 1 + dp[1]的最优解
• 当 coin=3 时，dp[6] = 1 + dp[3]的最优解

　　而：dp[i] = min(dp[i], 1+dp[i-coin]) 即为状态转移方程。

// LeetCode: 322. Coin Change

int coinChange(vector<int>& coins, int amount) {

    vector<int> dp(amount + 1, amount+1);

    dp[0] = 0;

    for (int i=0; i<dp.size(); i++) {

        for (int coin : coins) {

            if (i-coin < 0) continue;

            dp[i] = min(dp[i], 1+dp[i-coin]);

        }

    }

    return dp[amount] == amount+1 ? -1 : dp[amount];

}