第一节 序 斐波那契数列 Fibonacci 精通C语言 递归算法和动态规划

 第一节 序 斐波那契数列 Fibonacci

第一节 序 斐波那契数列         Fibonacci

第二节 0 1背包问题   0 1 Knapsack Problem

第三节 编辑距离         edit distance

第四节 子集总和         subset sum

第五节 钢条切割          cut rod

第六节 硬币找零          Coin Change

第七节 最长公共子序列         Longest Common Subsequence

第八节 矩阵链式乘法 Matrix Chain Multiplication

第九节 最优游戏策略 Optimal Strategy for a Game

第十节 最优二叉查找树         Optimal Binary Search Tree

第十一节 最长递增子序列 Longest Increasing Subsequence

动态规划是一种解决复杂问题的方法，它可以将其分解为更简单的子问题，一次解决每个子问题，然后将其解决方案存储在一个数组中（通常）。

现在，每次出现相同的子问题时，都无需使用重新计算其解决方案，而是使用先前计算的解决方案，从而以节省存储空间为代价来节省计算时间。

动态规划可以通过两种方式实现–记忆化，制表。

记忆–记忆使用自上而下的技术来解决问题，即从原始问题开始，然后将其分解为子问题，并以相同的方式解决这些子问题。在这种方法中，假设您已经计算了所有子问题。通常，您会从主要问题中执行递归调用（或某些迭代等效的调用）。您确保递归调用永远不会重新计算子问题，因为您缓存了结果，因此不会重新计算重复的子问题。

制表–制表是典型的动态规划方法。制表使用自下而上的方法来解决问题，即首先解决所有相关的子问题，通常是将结果存储在数组中。根据存储在数组中的结果，然后计算“顶部” /原始问题的解决方案。

记忆化和制表法都是用来避免重新计算子问题的存储技术。

示例–考虑一个生成第N个斐波那契数的程序。

Fib(n)=Fib(n-1)+Fib(n-2)

解决方案1 ​​–使用自上而下的方法而不进行动态规划

时间复杂度: T(n) = T(n-1) + T(n-2) O(2^n)

辅助空间复杂度: 考虑函数调用栈O(n), 否则 O(1).

int Fib(int n) 

{ 

     if(n<=1) 

     { 

          return n; 

     } 

     else 

     { 

          return (Fib(n-1) + Fib(n-2)); 

     } 

}

解决方案2 –使用自顶向下方法进行记忆化（动态规划）

时间复杂度为:O(n).

辅助空间复杂度: O(n), 函数调用栈O(n).

int Fibutil (int dp[], int n);

int Fib (int n)

{

    int *dp = (int *)malloc((n+1) * sizeof(int));

    for (int i = 0; i <= n; i++)

         dp[i] = -1;

    

    return Fibutil(dp, n);

}

int Fibutil (int dp[], int n) 

{ 

if (dp[n] == -1) 

{ 

if (n <= 1) 

dp[n] = n; 

else 

dp[n] = Fibutil(dp, n-1) + Fibutil(dp, n-2);

} 

return dp[n]; 

}

解决方案3 –自下而上的动态规划

时间复杂度为:O(n) .

辅助空间复杂度: O(n).

int Fib (int n)

{

    int *table = (int *)malloc((n+1) * sizeof(int));

    table[0] = 0;

    table[1] = 1;

    for (int i = 2; i <= n; i++)

        table[i] = table[i - 1] + table[i - 2];

    

    return table[n];

}

通常，动态规划的思想是解决一个给定的问题，方法是解决问题的不同部分（子问题），然后使用子问题的缓存解决方案获得整体解决方案。

动态规划的适用性-通过使用动态规划可以解决的问题具有以下两个主要属性：

重叠子问题，最优子结构

1）重叠子问题：

子问题重叠是一种属性，可以将问题分解为多次使用的子问题。

当需要一次又一次地解决相同子问题的解决方案时，主要使用动态规划。在动态规划中，子问题的计算解决方案存储在数组中，因此不必重新计算这些子问题。因此，当没有重叠的子问题时，动态规划就没有用，因为如果不再需要它们，则没有存储点的解决方案。

2）最优子结构

最优子结构是一种性质，可以根据子问题的最优解有效地构造原始问题的最优解。

如果给定的问题同时满足这两个属性，则可以使用动态规划解决问题。

解决DP问题的步骤-

1.以数学方式表达解决方案

2.递归表达解决方案

3.开发自下而上的算法或自上而下的记忆算法