动态规划:修订间差异

来自牛奶河Wiki
跳到导航 跳到搜索
无编辑摘要
无编辑摘要
第1行: 第1行:
动态规划(Dynamic Programming),是求解决策过程(decision process)最优化的数学方法。
动态规划(Dynamic Programming),是求解决策过程(decision process)最优化的数学方法。


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


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


==== 递归的暴力解法 ====
==== 递归的暴力解法 ====
  这个算法存在大量重复计算(重叠子问题),时间复杂度为 O(2^n)。
这个算法存在大量重复计算(重叠子问题),时间复杂度为 O(2^n)。
 
    // fibonacci
// fibonacci
    static int fb1(int N) {
 
        if (N == 1 || N == 2)
int fb(int N) {
            return 1;
 
        return fb1(N-1) + fb1(N-2);
   if (N == 1 || N == 2)
    }
 
       return 1;
 
   return fb(N-1) + fb(N-2);
 
}


==== 带备忘录的递归解法 ====
==== 带备忘录的递归解法 ====
  带「备忘录」的递归算法,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数,时间复杂度为 O(n),效率接近动态规划。
带「备忘录」的递归算法,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数,时间复杂度为 O(n),效率接近动态规划。
 
// fibonacci
// fibonacci
long fb(long N) {
 
    vector<long> f(N+1, 0);
long fb(long N) {
    f[1] = f[2] = 1;
 
    return helper(f, N);
    vector<long> f(N+1, 0);
}  
 
   f[1] = f[2] = 1;
long helper(vector<long>& f, long n) {
 
    if (n > 0 && f[n] == 0)
   return helper(f, N);  
        f[n] = helper(f, n-1) + helper(f, n-2);
 
    return f[n];
}  
}
 
以上两种解法,只处理了非零参数情况。执行时间如下:    
long helper(vector<long>& f, long n) {
time ./test_fb1 n=45
 
1134903170  
   if (n > 0 && f[n] == 0)  
real    0m17.511s
 
  user    0m17.076s
       f[n] = helper(f, n-1) + helper(f, n-2);
  sys    0m0.117s
 
   
   return f[n];
time ./test_fb2 n=45
 
1134903170
}
real    0m0.005s
 
user    0m0.000s
  以上两种解法,只处理了非零参数情况。执行时间如下:    
sys    0m0.005s
*time ./test_fb1 n=45
   
1134903170  
time ./test_fb2 n=66
 
27777890035288
real    0m17.511s   
real    0m0.002s
 
user    0m0.002s
user    0m17.076s   
sys    0m0.000s
 
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)
状态转移方程,是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第 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;


     }
如: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];
}


     return sum;
根据 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;
}


}


===== 最优子结构 =====
===== 最优子结构 =====

2024年4月17日 (三) 10:41的版本

动态规划(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];

}