动态规划

柔情只为你懂 2022-09-25 11:15 363阅读 0赞

动态规划的设计思想

动态规划（DP）[1]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结果。我们通过下面这个问题来说明这两个重要属性：重叠子问题和最优子结构。

重叠子问题

像分而治之，动态规划也把问题分解为子问题。动态规划主要用于：当相同的子问题的解决方案被重复利用。在动态规划中，子问题解决方案被存储在一个表中，以便这些不必重新计算。因此，如果这个问题是没有共同的（重叠）子问题， 动态规划是没有用的。例如，二分查找不具有共同的子问题。下面是一个斐波那契函数的递归函数，有些子问题被调用了很多次。

  1. /* simple recursive program for Fibonacci numbers */
  2. int fib(int n)
  3. {
  4.    if ( n <= 1 )
  5.       return n;
  6.    return fib(n-1) + fib(n-2);
  7. }

执行 fib(5) 的递归树

  1. fib(5)
  2.                      /             \
  3.                fib(4)                fib(3)
  4.              /      \                /     \
  5.          fib(3)      fib(2)         fib(2)    fib(1)
  6.         /     \        /    \       /    \
  7.   fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  8.   /    \
  9. fib(1) fib(0)

我们可以看到，函数f（3）被称执行2次。如果我们将存储f（3）的值，然后避免再次计算的话，我们会重新使用旧的存储值。有以下两种不同的方式来存储这些值，以便这些值可以被重复使用。

  • 记忆化（自上而下）
  • 打表（自下而上）

记忆化（自上而下）：

记忆化存储其实是对递归程序小的修改，作为真正的DP程序的过渡。我们初始化一个数组中查找所有初始值为零。每当我们需要解决一个子问题，我们先来看看这个数组(查找表)是否有答案。如果预先计算的值是有那么我们就返回该值，否则，我们计算该值并把结果在数组(查找表)，以便它可以在以后重复使用。

下面是记忆化存储程序：

  1. /* Memoized version for nth Fibonacci number */
  2. #include<stdio.h>
  3. #define NIL -1
  4. #define MAX 100
  6. int lookup[MAX];
  8. /* Function to initialize NIL values in lookup table */
  9. void _initialize()
  10. {
  11.   int i;
  12.   for (i = 0; i < MAX; i++)
  13.     lookup[i] = NIL;
  14. }
  16. /* function for nth Fibonacci number */
  17. int fib(int n)
  18. {
  19.    if(lookup[n] == NIL)
  20.    {
  21.     if ( n <= 1 )
  22.       lookup[n] = n;
  23.     else
  24.       lookup[n] = fib(n-1) + fib(n-2);
  25.    }
  27.    return lookup[n];
  28. }
  30. int main ()
  31. {
  32.   int n = 40;
  33.   _initialize();
  34.   printf("Fibonacci number is %d ", fib(n));
  35.   getchar();
  36.   return 0;
  37. }

打表（自下而上）

下面我们给出自下而上的打表方式，并返回表中的最后一项。

  1. /* tabulated version */
  2. #include<stdio.h>
  3. int fib(int n)
  4. {
  5.   int f[n+1];
  6.   int i;
  7.   f[0] = 0;   f[1] = 1; 
  8.   for (i = 2; i <= n; i++)
  9.       f[i] = f[i-1] + f[i-2];
  11.   return f[n];
  12. }
  14. int main ()
  15. {
  16.   int n = 9;
  17.   printf("Fibonacci number is %d ", fib(n));
  18.   getchar();
  19.   return 0;
  20. }

这两种方法都能存储子问题解决方案。在第一个版本中，记忆化存储只在查找表存储需要的答案。而第二个版本，所有子问题都会被存储到查找表中，不管是否是必须的。比如LCS问题的记忆化存储版本，并不会存储不必要的子问题答案。

最优子结构[2]

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

例如，最短路径问题有以下最优子结构性质：如果一个节点x是到源节点ü的最短路径，同时又是到目的节点V的最短路径，则最短路径从u到v是结合最短路径：u到x和x到v。解决任意两点间的最短路径的算法的Floyd-Warshall算法[3]和贝尔曼-福特[4]是动态规划的典型例子。

另一方面最长路径问题不具有最优子结构性质。这里的最长路径是指两个节点之间最长简单路径（路径不循环）。

考虑下算法导论上面的例子：

这里写图片描述
有两条最长的路径与Q到T：Q – > R – > T和Q – > S-> T。不像最短路径，这些路径最长不具有最优子属性。例如，最长路径q-> r-> t不是由q->r 和 r->t的组合 ，因为最长的路径从q至r为q-> s-> t->r

动态规划算法的设计要素

这里用一个矩阵链乘问题为例说明动态规划算法的设计要素。

例如：给定n个矩阵{ A1,A2,…,A**n}，其中A**i与A**i+1是可乘的，i=1,2,…,n−1。考察这n个矩阵的连乘积A1A2…A**n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。

例如，如果我们有四个矩阵A，B，C和D，我们将有：

(A**B)C=A(B**C）=(A**C)B=….
不同组合得到的运算次数是不同的，例如A为 10 × 30 , B为 30 × 5 , C 为 5 × 60 ,那么,如果采用第一种次序，执行的基本运算次数是：
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500
而采用第二种次序，执行的基本运算次数是：
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000
很明显第一种运算更为高效。

问题：给定一个数组P[]表示矩阵的链，使得第i个矩阵Ai 的维数为 p[i-1] x p[i].。我们需要写一个函数MatrixChainOrder（）返回这个矩阵连相乘最小的运算次数。

示例：

  1. 输入：P [] = {40，20，30，10，30}   
  2. 输出：26000  
  3. 有4个矩阵维数为 40X20，20X30，30×10和10X30。
  4. 运算次数最少的计算方式为：
  5. （A（BC））D  - > 20 * 30 * 10 +40 * 20 * 10 +40 * 10 * 30
  7. 输入：P[] = {10，20，30，40，30} 
  8. 输出：30000
  9. 有4个矩阵维数为 10×20，20X30，30X40和40X30。 
  10. 运算次数最少的计算方式为：
  11.   （（AB）C）D  - > 10 * 20 * 30 +10 * 30 * 40 +10 * 40 * 30

最优子结构：

一个简单的解决办法是把括号放在所有可能的地方，计算每个位置的成本，并返回最小值。对于一个长度为n的链，我们有n-1种方法放置第一组括号。

例如，如果给定的链是4个矩阵。让矩阵连为ABCD，则有3种方式放第一组括号：A（BCD），（AB）CD和（ABC）D。

所以，当我们把一组括号，我们把问题分解成更小的尺寸的子问题。因此，这个问题具有最优子结构性质，可以使用递归容易解决。

2）重叠子问题
以下是递归的实现，只需用到上面的最优子结构性质。

  1. //直接的递归解决
  2. #include<stdio.h>
  3. #include<limits.h>
  4. //矩阵 Ai 的维数为 p[i-1] x p[i] ( i = 1..n )
  5. int MatrixChainOrder(int p[], int i, int j)
  6. {
  7.     if(i == j)
  8.         return 0;
  9.     int k;
  10.     int min = INT_MAX;
  11.     int count;
  13.     // 在第一个和最后一个矩阵直接放置括号
  14.     //递归计算每个括号，并返回最小的值
  15.     for (k = i; k <j; k++)
  16.     {
  17.         count = MatrixChainOrder(p, i, k) +
  18.                 MatrixChainOrder(p, k+1, j) +
  19.                 p[i-1]*p[k]*p[j];
  21.         if (count < min)
  22.             min = count;
  23.     }
  25.     return min;
  26. }
  28. // 测试
  29. int main()
  30. {
  31.     int arr[] = {
  32.    1, 2, 3, 4, 3};
  33.     int n = sizeof(arr)/sizeof(arr[0]);
  34.     printf("Minimum number of multiplications is %d ", 
  35.                           MatrixChainOrder(arr, 1, n-1));
  37.     getchar();
  38.     return 0;
  39. }

上面直接的递归方法的复杂性是指数级。当然可以用记忆化存储优化。应当指出的是，上述函数反复计算相同的子问题。请参阅下面的递归树的大小4的矩阵链。函数MatrixChainOrder（3，4）被调用两次。我们可以看到，有许多子问题被多次调用。

这里写图片描述

动态规划解决方案
以下是C / C + +实现，使用动态规划矩阵链乘法问题。

  1. #include<stdio.h>
  2. #include<limits.h>
  4. int MatrixChainOrder(int p[], int n)
  5. {
  7.     /* 第0行第0列其实没用到 */
  8.     int m[n][n];
  10.     int i, j, k, L, q;
  12.     //单个矩阵相乘，所需数乘次数为0
  13.     for (i = 1; i < n; i++)
  14.         m[i][i] = 0;
  16.      //以下两个循环是关键之一，以6个矩阵为例(为描述方便，m[i][j]用ij代替)
  17.      //需按照如下次序计算
  18.      //01 12 23 34 45
  19.      //02 13 24 35
  20.      //03 14 25
  21.      //04 15
  22.      //05
  23.      //下面行的计算结果将会直接用到上面的结果。例如要计算14，就会用到12，24；或者13，34等等
  24.     for (L=2; L<n; L++)   
  25.     {
  26.         for (i=1; i<=n-L+1; i++)
  27.         {
  28.             j = i+L-1;
  29.             m[i][j] = INT_MAX;
  30.             for (k=i; k<=j-1; k++)
  31.             {
  32.                 q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
  33.                 if (q < m[i][j])
  34.                     m[i][j] = q;
  35.             }
  36.         }
  37.     }
  39.     return m[1][n-1];
  40. }
  42. int main()
  43. {
  44.     int arr[] = {
  45.    1, 2, 3, 4};
  46.     int size = sizeof(arr)/sizeof(arr[0]);
  48.     printf("Minimum number of multiplications is %d ",
  49.                        MatrixChainOrder(arr, size));
  51.     getchar();
  52.     return 0;
  53. }

时间复杂度: O(n3)
空间复杂度: O(n2)

动态规划算法典型的应用

最长递增子序列LIS

最长递增子序列LIS[5]的问题可以使用动态规划要解决的问题，例如，最长递增子序列（LIS）的问题是要找到一个给定序列的最长子序列的长度，使得子序列中的所有元素被排序的顺序增加。例如，{10，22，9，33，21，50，41，60，80} LIS的长度是6和 LIS为{10，22，33，50，60，80}。

1) 最优子结构

对于长度为N的数组A[N]={ a0,a1,a2,…,a**n−1}，假设假设我们想求以aj结尾的最大递增子序列长度，设为L[j]，那么L[j] = max(L[i]) + 1, where i < j && a[i] < a[j], 也就是i的范围是0到j – 1。这样，想求aj结尾的最大递增子序列的长度，我们就需要遍历j之前的所有位置i（0到j-1），找出a[i] < a[j]，计算这些i中，能产生最大L[i]的i，之后就可以求出L[j]。之后我对每一个A[N]中的元素都计算以他们各自结尾的最大递增子序列的长度，这些长度的最大值，就是我们要求的问题——数组A的最大递增子序列。

2) 重叠子问题

以下是简单的递归实现LIS问题(先不说性能和好坏，后面讨论)。这个实现我们遵循上面提到的递归结构。使用 max_ending_here 返回 每一个LIS结尾的元素，结果LIS是使用指针变量返回。

  1. /* LIS 简单的递归实现 */
  2. #include<stdio.h>
  3. #include<stdlib.h>
  5. /* 要利用递归调用，此函数必须返回两件事情：
  6.    1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose
  7.    2) Overall maximum as the LIS may end with an element before arr[n-1]  max_ref is used this purpose.
  8. The value of LIS of full array of size n is stored in *max_ref which is our final result
  9. */
  10. int _lis( int arr[], int n, int *max_ref)
  11. {
  12.     /* Base case */
  13.     if(n == 1)
  14.         return 1;
  16.     int res, max_ending_here = 1; // 以arr[n-1]结尾的 LIS的长度
  18.     /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If 
  19.        arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
  20.        to be updated, then update it */
  21.     for(int i = 1; i < n; i++)
  22.     {
  23.         res = _lis(arr, i, max_ref);
  24.         if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
  25.             max_ending_here = res + 1;
  26.     }
  28.     // Compare max_ending_here with the overall max. And update the
  29.     // overall max if needed
  30.     if (*max_ref < max_ending_here)
  31.        *max_ref = max_ending_here;
  33.     // Return length of LIS ending with arr[n-1]
  34.     return max_ending_here;
  35. }
  37. // The wrapper function for _lis()
  38. int lis(int arr[], int n)
  39. {
  40.     // The max variable holds the result
  41.     int max = 1;
  43.     // The function _lis() stores its result in max
  44.     _lis( arr, n, &max );
  46.     // returns max
  47.     return max;
  48. }
  50. /* 测试上面的函数 */
  51. int main()
  52. {
  53.     int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
  54.     int n = sizeof(arr)/sizeof(arr[0]);
  55.     printf("Length of LIS is %d\n",  lis( arr, n ));
  56.     getchar();
  57.     return 0;
  58. }

根据上面的实现方式，以下是递归树大小4的调用。LIS（N）为我们返回arr[]数组的LIS长度。

  1. lis(4)           
  2.                  /       |      \
  3.          lis(3)      lis(2)    lis(1)  
  4.         /     \        /         
  5.   lis(2)  lis(1)   lis(1) 
  6.   /    
  7. lis(1)

我们可以看到，有些重复的子问题被多次计算。所以我们可以使用memoization (记忆化存储)的或打表 来避免同一子问题的重新计算。以下是打表方式实现的LIS。

  1. /* LIS 的动态规划方式实现*/
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. /* lis() returns the length of the longest increasing subsequence in 
  5.     arr[] of size n */
  6. int lis( int arr[], int n )
  7. {
  8.    int *lis, i, j, max = 0;
  9.    lis = (int*) malloc ( sizeof( int ) * n );
  11.    /* Initialize LIS values for all indexes */
  12.    for ( i = 0; i < n; i++ )
  13.       lis[i] = 1;
  15.    /* Compute optimized LIS values in bottom up manner */
  16.    for ( i = 1; i < n; i++ )
  17.       for ( j = 0; j < i; j++ )
  18.          if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
  19.             lis[i] = lis[j] + 1;
  21.    /* Pick maximum of all LIS values */
  22.    for ( i = 0; i < n; i++ )
  23.       if ( max < lis[i] )
  24.          max = lis[i];
  26.    /* Free memory to avoid memory leak */
  27.    free( lis );
  29.    return max;
  30. }
  32. /* 测试程序 */
  33. int main()
  34. {
  35.   int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
  36.   int n = sizeof(arr)/sizeof(arr[0]);
  37.   printf("Length of LIS is %d\n", lis( arr, n ) );
  39.   getchar();
  40.   return 0;
  41. }

注意，上面动态的DP解决方案的时间复杂度为O（n2），其实较好的解决方案是O(nlogn)

最长公共子序列LCS

LCS问题[6] [7]描述:给定两个序列，找出在两个序列中同时出现的最长子序列的长度。一个子序列是出现在相对顺序的序列，但不一定是连续的。例如，“ABC”，“ABG”，“BDF”，“AEG”，“acefg“，..等都是”ABCDEFG“ 序列。因此，长度为n的字符串有2n个不同的可能的序列。

注意:

最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence, LCS）的区别：子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。

这是一个典型的计算机科学问题，基础差异（即输出两个文件之间的差异文件比较程序），并在生物信息学有较多应用。例如：输入序列“ABCDGH”和“AEDFHR” 的LCS是“ADH”长度为3；输入序列“AGGTAB”和“GXTXAYB”的LCS是“GTAB”长度为4。

这个问题的直观的解决方案是同时生成给定序列的所有子序列，找到最长匹配的子序列。此解决方案的复杂性是指数的。让我们来看看如何这个问题 （拥有动态规划（DP）问题的两个重要特性）：

1）最优子结构：

设输入序列是X[0..m−1]和Y[0..n−1]，长度分别为m和n。和设序列L(X[0..m−1]，Y[0..n−1]）是这两个序列的LCS的长度。

以下为L（X[0..M−1]，Y[0..N−1]）的递归定义：

  • 如果两个序列的最后一个元素匹配（即X [M-1] == Y [N-1]）
    L（X[0..M−1]，Y[0..N−1]）=1+L（X[0..M−2]，Y[0..N−1]）
  • 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
    L（X[0..M−1]，Y[0..N−1]）=MAX（L（X[0..M−2]，Y[0..N−1]），L（X[0..M−1]，Y[0..N−2]）

例：
1）考虑输入字符串“AGGTAB”和“GXTXAYB”。最后一个字符匹配的字符串。这样的LCS的长度可以写成：
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)

2）考虑输入字符串“ABCDGH”和“AEDFHR。最后字符不为字符串相匹配。这样的LCS的长度可以写成：
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )

因此，LCS问题有最优子结构性质！

2）重叠子问题：

以下是直接的递归实现， 遵循上面提到的递归结构。

  1. /* 简单的递归实现LCS问题 */
  2. #include<stdio.h>
  3. #include<stdlib.h>
  5. int max(int a, int b);
  7. /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
  8. int lcs( char *X, char *Y, int m, int n )
  9. {
  10.    if (m == 0 || n == 0)
  11.      return 0;
  12.    if (X[m-1] == Y[n-1])
  13.      return 1 + lcs(X, Y, m-1, n-1);
  14.    else
  15.      return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
  16. }
  18. /* Utility function to get max of 2 integers */
  19. int max(int a, int b)
  20. {
  21.     return (a > b)? a : b;
  22. }
  24. /* 测试上面的函数 */
  25. int main()
  26. {
  27.   char X[] = "AGGTAB";
  28.   char Y[] = "GXTXAYB";
  30.   int m = strlen(X);
  31.   int n = strlen(Y);
  33.   printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );
  35.   getchar();
  36.   return 0;
  37. }

上面直接的递归方法的时间复杂度为O（2n）.(在最坏的情况下。X和Y不匹配的所有字符即LCS的长度为0)。按照到上述的实现，下面是对输入字符串“AXY**T”和“AYZ**X”的部分递归树：

  1. lcs("AXYT", "AYZX")
  2.                        /                 \
  3.          lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
  4.          /            \                  /               \
  5. lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

在上述部分递归树，LCS（“AXY”，“AYZ”）被调用两次。如果我们绘制完整的递归树，那么我们可以看到，我们可以看到很多重复的调用。所以这个问题有重叠的子结构性质，可使用memoization的或打表来避免重新计算。下面是用动态规划(打表)解决LCS问题:

  1. / *动态规划实现的LCS问题* /
  2. #include<stdio.h>
  3. #include<stdlib.h>
  5. int max(int a, int b);
  7. /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
  8. int lcs( char *X, char *Y, int m, int n )
  9. {
  10.    int L[m+1][n+1];
  11.    int i, j;
  13.    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
  14.       that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
  15.    for (i=0; i<=m; i++)
  16.    {
  17.      for (j=0; j<=n; j++)
  18.      {
  19.        if (i == 0 || j == 0)
  20.          L[i][j] = 0;
  22.        else if (X[i-1] == Y[j-1])
  23.          L[i][j] = L[i-1][j-1] + 1;
  25.        else
  26.          L[i][j] = max(L[i-1][j], L[i][j-1]);
  27.      }
  28.    }
  30.    /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
  31.    return L[m][n];
  32. }
  34. /* Utility function to get max of 2 integers */
  35. int max(int a, int b)
  36. {
  37.     return (a > b)? a : b;
  38. }
  40. /*测试上面的函数 */
  41. int main()
  42. {
  43.   char X[] = "AGGTAB";
  44.   char Y[] = "GXTXAYB";
  46.   int m = strlen(X);
  47.   int n = strlen(Y);
  49.   printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );
  51.   getchar();
  52.   return 0;
  53. }

最长回文子序列

问题[8]:给一个字符串，找出它的最长的回文子序列的长度。例如，如果给定的序列是“BBABCBCAB”，则输出应该是7，“BABCBAB”是在它的最长回文子序列。 “BBBBB”和“BBCBB”也都是该字符串的回文子序列，但不是最长的。注意和最长回文子串的区别(参考：最长回文串)！这里说的子序列，类似最长公共子序列LCS( Longest Common Subsequence)问题，可以是不连续的。这就是LPS(Longest Palindromic Subsequence)问题。

最直接的解决方法是：生成给定字符串的所有子序列，并找出最长的回文序列，这个方法的复杂度是指数级的。下面来分析怎么用动态规划解决。

1）最优子结构

假设 X[0 … n-1] 是给定的序列，长度为n. 让 L(0,n-1) 表示 序列 X[0 … n-1] 的最长回文子序列的长度。

  • 如果X的最后一个元素和第一个元素是相同的，这时：L(0,n−1)=L(1,n−2)+2 , 还以 “BBABCBCAB” 为例，第一个和最后一个相同，因此 L(1,n-2) 就表示红色的部分。
  • 如果不相同：L(0, n-1) = MAX ( L(1, n-1) , L(0, n-2) )。 以”BABCBCA” 为例，L(1,n-1)即为去掉第一个元素的子序列，L(0, n-2)为去掉最后一个元素。

有了上面的公式，可以很容易的写出下面的递归程序：

  1. #include<stdio.h>
  2. #include<string.h>
  3. int lps(char *seq, int i, int j)
  4. {
  5.    //一个元素即为1
  6.    if (i == j)
  7.      return 1;
  8.    if(i > j) return 0; //因为只计算序列 seq[i ... j]
  10.    // 如果首尾相同
  11.    if (seq[i] == seq[j])
  12.       return lps (seq, i+1, j-1) + 2;
  14.    // 首尾不同
  15.    return max( lps(seq, i, j-1), lps(seq, i+1, j) );
  16. }
  18. /* 测试 */
  19. int main()
  20. {
  21.     char seq[] = "acmerandacm";
  22.     int n = strlen(seq);
  23.     printf ("The lnegth of the LPS is %d", lps(seq, 0, n-1));
  24.     getchar();
  25.     return 0;
  26. }

Output: The lnegth of the LPS is 5 (即为: amama)

2) 重叠子问题

画出上面程序的递归树(部分)，已一个长度为6 的字符串为例：

  1. L(0, 5)
  2.           /          \  
  3.       L(1,5)          L(0,4)
  4.     /      \          /      \
  5. L(2,5)    L(1,4)  L(1,4)  L(0,3)

可见有许多重复的计算，例如L(1,4)。该问题符合动态规划的两个主要性质: 重叠子问题 和 最优子结构 。下面通过动态规划的方法解决，通过自下而上的方式打表，存储子问题的最优解。

  1. int lpsDp(char * str,int n){
  2.     int dp[n][n], tmp;
  3.     memset(dp,0,sizeof(dp));
  4.     for(int i=0; i<n; i++) dp[i][i] = 1;
  5.     // i 表示 当前长度为 i+1的 子序列
  6.     for(int i=1; i<n; i++){
  7.         tmp = 0;
  8.         //考虑所有连续的长度为i+1的子串. 该串为 str[j, j+i]
  9.         for(int j=0; j+i<n; j++){
  10.             //如果首尾相同
  11.             if(str[j] == str[j+i]){
  12.                 tmp = dp[j+1][j+i-1] + 2;
  13.             }else{
  14.                 tmp = max(dp[j+1][j+i],dp[j][j+i-1]);
  15.             }
  16.             dp[j][j+i] = tmp;
  17.         }
  18.     }
  19.     //返回串 str[0][n-1] 的结果
  20.     return dp[0][n-1];
  21. }

该算法的时间复杂度为O(n2)。其实这个问题和 最长公共子序列 问题有些相似之处，我们可以对LCS算法做些修改，来解决此问题:

  • 1) 对给定的字符串逆序 存储在另一个数组 rev[] 中
  • 2) 再求这两个 字符串的 LCS的长度

时间复杂度也为O(n2)。

最小编辑距离(Edit Distance)

问题：给定一个长度为m和n的两个字符串，设有以下几种操作：替换（R），插入（I）和删除（D）且都是相同的操作。寻找到转换一个字符串插入到另一个需要修改的最小（操作）数量。

PS：最短编辑距离算法右许多实际应用，参考Lucene[9]的 API。另一个例子，对一个字典应用，显示最接近给定单词\正确拼写单词的所有单词。

找递归函数：

这个案例的子问题是什么呢？考虑寻找的他们的前缀子串的编辑距离，让我们表示他们为[1…i]和[1….j] , 1<i<m 和1<j<n.显然，这是解决最终问题的子问题，记为E（i，j）。我们的目标是找到E（m，n）和最小的编辑距离。

我们可以用三种方式:(i,−), (−,j)和(i,j)右对齐两个前缀字符串。连字符符号（–）表示没有字符。

看一个例子或许会更清楚：假设给定的字符串是 SUNDAY 和 SATURDAY。如果i=2 , j=4，即前缀字符串分别是SU和SATU（假定字符串索引从1开始）。这两个字串最右边的字符可以用三种不同的方式对齐：

  1. (i,j): 对齐字符U和U。他们是相等的，没有修改的必要。我们仍然留下其中i=1和j=3，即问题E（1,3）
  2. (i, -) : 对第一个字符串右对齐，第二字符串最右为空字符。我们需要一个删除（D）操作。我们还留下其中i = 1和j = 4的 子问题 E（i-1，j）。
  3. (-, j) : 对第二个字符串右对齐，第一个字符串最右为空字符。在这里，我们需要一个插入（I）操作。我们还留下了子问题i=2 和 j=3，E（i，j−1）。

对于这三种操作，我可以得到最少的操作为：

E(i,j)=min([E(i−1,j)+D],[E(i,j−1)+I],[E(i−1,j−1)+R])

其中,E(i−1,j−1)+R表示：如果 i,j 字符不一样.到这里还没有做完。什么将是基本情况？

当两个字符串的大小为0，其操作距离为0。当其中一个字符串的长度是零，需要的操作距离就是另一个字符串的长度. 即：

E（0，0）=0，E（i，0）=i，E（0，j）=j

为基本情况。这样就可以完成递归程序了。

动态规划解法：

我们先计算出上面递归表达式的时间复杂度：T(m,n)=T(m−1,n−1)+T(m,n−1)+T(m−1,n)+C. T（m，n）的复杂性，可以通过连续替代方法或结二元齐次方程计算。结果是指数级的复杂度。这是显而易见的，从递归树可以看出这将是一次又一次地解决子问题。

我们对重复子问题的结果打表存储，并在有需要时（自下而上）查找。动态规划的解法时间复杂度为 O(m**n) 正是我们打表的时间.通常情况下，D，I和R操作的成本是不一样的。在这种情况下，该问题可以表示为一个有向无环图（DAG）与各边的权重，并且找到最短路径给出编辑距离。

实现代码如下：

  1. // 动态规划实现 最小编辑距离
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<string.h>
  6. // 测试字符串
  7. #define STRING_X "SUNDAY"
  8. #define STRING_Y "SATURDAY"
  10. #define SENTINEL (-1)
  11. #define EDIT_COST (1)
  13. inline
  14. int min(int a, int b) {
  15.    return a < b ? a : b;
  16. }
  18. // Returns Minimum among a, b, c
  19. int Minimum(int a, int b, int c)
  20. {
  21.     return min(min(a, b), c);
  22. }
  24. // Strings of size m and n are passed.
  25. // Construct the Table for X[0...m, m+1], Y[0...n, n+1]
  26. int EditDistanceDP(char X[], char Y[])
  27. {
  28.     // Cost of alignment
  29.     int cost = 0;
  30.     int leftCell, topCell, cornerCell;
  32.     int m = strlen(X)+1;
  33.     int n = strlen(Y)+1;
  35.     // T[m][n]
  36.     int *T = (int *)malloc(m * n * sizeof(int));
  38.     // Initialize table
  39.     for(int i = 0; i < m; i++)
  40.         for(int j = 0; j < n; j++)
  41.             *(T + i * n + j) = SENTINEL;
  43.     // Set up base cases
  44.     // T[i][0] = i
  45.     for(int i = 0; i < m; i++)
  46.         *(T + i * n) = i;
  48.     // T[0][j] = j
  49.     for(int j = 0; j < n; j++)
  50.         *(T + j) = j;
  52.     // Build the T in top-down fashion
  53.     for(int i = 1; i < m; i++)
  54.     {
  55.         for(int j = 1; j < n; j++)
  56.         {
  57.             // T[i][j-1]
  58.             leftCell = *(T + i*n + j-1);
  59.             leftCell += EDIT_COST; // deletion
  61.             // T[i-1][j]
  62.             topCell = *(T + (i-1)*n + j);
  63.             topCell += EDIT_COST; // insertion
  65.             // Top-left (corner) cell
  66.             // T[i-1][j-1]
  67.             cornerCell = *(T + (i-1)*n + (j-1) );
  69.             // edit[(i-1), (j-1)] = 0 if X[i] == Y[j], 1 otherwise
  70.             cornerCell += (X[i-1] != Y[j-1]); // may be replace
  72.             // Minimum cost of current cell
  73.             // Fill in the next cell T[i][j]
  74.             *(T + (i)*n + (j)) = Minimum(leftCell, topCell, cornerCell);
  75.         }
  76.     }
  78.     // 结果存储在 T[m][n]
  79.     cost = *(T + m*n - 1);
  80.     free(T);
  81.     return cost;
  82. }
  84. // 递归方法实现
  85. int EditDistanceRecursion( char *X, char *Y, int m, int n )
  86. {
  87.     // 基本情况
  88.     if( m == 0 && n == 0 )
  89.         return 0;
  91.     if( m == 0 )
  92.         return n;
  94.     if( n == 0 )
  95.         return m;
  97.     // Recurse
  98.     int left = EditDistanceRecursion(X, Y, m-1, n) + 1;
  99.     int right = EditDistanceRecursion(X, Y, m, n-1) + 1;
  100.     int corner = EditDistanceRecursion(X, Y, m-1, n-1) + (X[m-1] != Y[n-1]);
  102.     return Minimum(left, right, corner);
  103. }
  105. int main()
  106. {
  107.     char X[] = STRING_X; // vertical
  108.     char Y[] = STRING_Y; // horizontal
  110.     printf("Minimum edits required to convert %s into %s is %d\n",
  111.            X, Y, EditDistanceDP(X, Y) );
  112.     printf("Minimum edits required to convert %s into %s is %d by recursion\n",
  113.            X, Y, EditDistanceRecursion(X, Y, strlen(X), strlen(Y)));
  115.     return 0;
  116. }

给出了动态规划实现 和 递归实现。大家可以比较他们的效率差异。

硬币找零问题

问题[10] [11]：假设有m种面值不同的硬币，个个面值存于数组S={ S1，S2，…S**m}中，现在用这些硬币来找钱，各种硬币的使用个数不限。 求对于给定的钱数N，我们最多有几种不同的找钱方式。硬币的顺序并不重要。

例如，对于N = 4，S = {1,2,3}，有四种方案：{1,1,1,1}，{1,1,2}，{2,2}，{1， 3}。所以输出应该是4。对于N = 10，S = {2,5, 3,6}，有五种解决办法：{2,2,2,2,2}，{2,2,3,3}，{2,2,6 }，{2,3,5}和{5,5}。所以输出应该是5。

1）最优子结构

要算总数的解决方案，我们可以把所有的一整套解决方案在两组 (其实这个方法在组合数学中经常用到，要么包含某个元素要么不包含，用于递推公式等等，)。

  1. 解决方案不包含 第m种硬币（或S**m）。

    • 解决方案包含至少一个 第m种硬币。让数（S [] , M, N）是该函数来计算解的数目，则它可以表示为计数的总和（S [], M-1, N）和计数（S[]，M，N−S**m）。

    • 因此，这个问题具有最优子结构性质的问题。

      2) 重叠子问题

      下面是一个简单的递归实现硬币找零问题。遵循上面提到的递归结构。

      1. #include<stdio.h>
      2. int count( int S[], int m, int n )
      3. {
      4.     // 如果n为0，就找到了一个方案
      5.     if (n == 0)
      6.         return 1;
      7.     if (n < 0)
      8.         return 0;
      9.     // 没有硬币可用了，也返回0
      10.     if (m <=0 )
      11.         return 0;
      12.     // 按照上面的递归函数
      13.     return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
      14. }
      16. // 测试
      17. int main()
      18. {
      19.     int i, j;
      20.     int arr[] = {
      21.        1, 2, 3};
      22.     int m = sizeof(arr)/sizeof(arr[0]);
      23.     printf("%d ", count(arr, m, 4));
      24.     getchar();
      25.     return 0;
      26. }

      应当指出的是，上述函数反复计算相同的子问题。见下面的递归树为S = {1，2，3}，且n = 5。
      的函数C（{1}，3）被调用两次。如果我们绘制完整的树，那么我们可以看到，有许多子问题被多次调用。

      1. C() --> count()
      2.                               C({1,2,3}, 5)                     
      3.                            /                \
      4.                          /                   \              
      5.              C({1,2,3}, 2)                 C({1,2}, 5)
      6.             /     \                        /         \
      7.            /        \                     /           \
      8. C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)
      9.                /     \            /    \            /     \
      10.              /        \          /      \          /       \
      11.     C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)
      12.                    / \      / \       / \        /     \    
      13.                   /   \    /   \     /   \      /       \ 
      14.                 .      .  .     .   .     .   C({1}, 3) C({}, 4)
      15.                                                /  \
      16.                                               /    \  
      17.                                              .      .

      所以，硬币找零问题具有符合动态规划的两个重要属性。像其他典型的动态规划（DP）的问题，可通过自下而上的方式打表，存储相同的子问题。当然上面的递归程序也可以改写成记忆化存储的方式来提高效率。

      下面是动态规划的程序：

      1. #include<stdio.h>
      3. int count( int S[], int m, int n )
      4. {
      5.     int i, j, x, y;
      7.     // 通过自下而上的方式打表我们需要n+1行
      8.     // 最基本的情况是n=0
      9.     int table[n+1][m];
      11.     // 初始化n=0的情况 (参考上面的递归程序)
      12.     for (i=0; i<m; i++)
      13.         table[0][i] = 1;
      15.     for (i = 1; i < n+1; i++)
      16.     {
      17.         for (j = 0; j < m; j++)
      18.         {
      19.             // 包括 S[j] 的方案数
      20.             x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
      22.             // 不包括 S[j] 的方案数
      23.             y = (j >= 1)? table[i][j-1]: 0;
      25.             table[i][j] = x + y;
      26.         }
      27.     }
      28.     return table[n][m-1];
      29. }
      31. // 测试
      32. int main()
      33. {
      34.     int arr[] = {
      35.        1, 2, 3};
      36.     int m = sizeof(arr)/sizeof(arr[0]);
      37.     int n = 4;
      38.     printf(" %d ", count(arr, m, n));
      39.     return 0;
      40. }

      时间复杂度：O(m**n)

      以下为上面程序的优化版本。这里所需要的辅助空间为O(n)。因为我们在打表时，本行只和上一行有关，类似01背包问题。

      1. int count( int S[], int m, int n )
      2. {
      3.     int table[n+1];
      4.     memset(table, 0, sizeof(table));
      5.     //初始化基本情况
      6.     table[0] = 1;
      8.     for(int i=0; i<m; i++)
      9.         for(int j=S[i]; j<=n; j++)
      10.             table[j] += table[j-S[i]];
      12.     return table[n];
      13. }

      0-1背包问题

      问题[12]:在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……W**n，与之相对应的价值为P1,P2……P**n。求出获得最大价值的方案。

      注意：在本题中，所有的体积值均为整数。01的意思是，每个物品都是一个整体，要么整个都要，要么都不要。

      1）最优子结构

      考虑所有物品的子集合，考虑第n个物品都有两种情况: 一种情况： 包括在最优方案中 ；二 种情况：不在最优方案中。因此，能获得的最大价值，即为以下两个值中较大的那个

      • 1) 在剩下 n−1个物品中(剩余 W 重量可用)的情况能得到的最大价值 (即排除了 第n个物品)
      • 2) 第n个物品的价值加上剩下 剩下的 n−1 个物品(剩余W−w**n的重量)能得到的最大价值。(即包含了第n个物品)

      如果第n个物品的重量，超过了当前的剩余重量W，那么只能选情况1)， 排除第n个物品。

      2) 重叠子问题

      下面是一个递归的实现，按照上面的最优子结构。

      1. /* 朴素的递归实现  0-1 背包 */
      2. #include<stdio.h>
      4. int max(int a, int b) { return (a > b)? a : b; }
      6. // 返回  前n个物品在容量为W时，能得到的最大价值
      7. int knapSack(int W, int wt[], int val[], int n)
      8. {
      9.    // 没有物品了
      10.    if (n == 0 || W == 0)
      11.        return 0;
      13.    // 如果当前第n个物品超重了，就排除在外
      14.    if (wt[n-1] > W)
      15.        return knapSack(W, wt, val, n-1);
      17.    //返回两种情况下最大的那个 (1) 包括第n个物品 (2) 不包括第n个物品
      18.    else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
      19.                     knapSack(W, wt, val, n-1)
      20.                   );
      21. }
      23. // 测试
      24. int main()
      25. {
      26.     int val[] = {
      27.        60, 100, 120};
      28.     int wt[] = {
      29.        10, 20, 30};
      30.     int  W = 50;
      31.     int n = sizeof(val)/sizeof(val[0]);
      32.     printf("%d", knapSack(W, wt, val, n));
      33.     return 0;
      34. }

      这种方法其实就是搜索了所有的情况，但是有很多重复的计算。时间复杂度是指数级的 O(2n)。

      1. 在下面的递归树中 K() 代表 knapSack().  
      2. 输入数据如下：
      3. wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}
      5.                        K(3, 2)         ---------> K(n, W)
      6.                    /            \ 
      7.                  /                \               
      8.             K(2,2)                  K(2,1)
      9.           /       \                  /    \ 
      10.         /           \              /        \
      11.        K(1,2)      K(1,1)        K(1,1)     K(1,0)
      12.        /  \         /   \          /   \
      13.      /      \     /       \      /       \
      14. K(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)

      可见相同的子问题被计算多次。01背包满足动态规划算法的两个基本属性(重叠子问题和最优子结构)。可以通过自下而上的打表，存储中间结果，来避免重复计算。动态规划解法如下：

      1. #include<stdio.h>
      2. int max(int a, int b) { return (a > b)? a : b; }
      4. int knapSack(int W, int wt[], int val[], int n)
      5. {
      6.    int i, w;
      7.    int dp[n+1][W+1];
      9.    for (i = 0; i <= n; i++)
      10.    {
      11.        for (w = 0; w <= W; w++)
      12.        {
      13.            if (i==0 || w==0)
      14.                dp[i][w] = 0;
      15.            else if (wt[i-1] <= w)
      16.                  dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],  dp[i-1][w]);
      17.            else
      18.                  dp[i][w] = dp[i-1][w];
      19.        }
      20.    }
      21.    return dp[n][W];
      22. }
      24. int main()
      25. {
      26.     int val[] = {
      27.        80, 100, 150};
      28.     int wt[] = {
      29.        10, 20, 30};
      30.     int  W = 50;
      31.     int n = sizeof(val)/sizeof(val[0]);
      32.     printf("%d", knapSack(W, wt, val, n));
      33.     return 0;
      34. }

      空间复杂度和时间复杂度都为O(W**n). 由于打表的过程中，计算的当前行只依赖上一行，空间复杂度可以优化为O(W).

      划分问题

      划分问题是指有一个集合，判断是否可以把这个结合划分为总和相等的两个集合。例如：arr[] = {1, 5, 11, 5},Output: true.这个数组可以划分为： {1, 5, 5} 和 {11}. arr[] = {1, 5, 3}Output: false.无法划分为总和相等的两部分

      如果划分后的两个集合总和相等，则原集合的总和肯定为偶数，假设为总和为sum。问题即为是否有子集合的总和为sum/2.

      递归解决

      设函数isSubsetSum(arr, n, sum/2) 返回true如果存在arr的一个子集合的总和为 sum/2
      isSubsetSum函数为分为下面两个子问题

      • 1) 不考虑最后一个元素。问题递归到 isSubsetSum(arr, n-1. sum/2)
      • 2) 考虑最后一个元素。问题递归到 isSubsetSum(arr, n-1. sum/2-arr[n])

      上面两种情况有一个返回TRUE,即可

      1. isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
      2. isSubsetSum (arr, n-1, sum/2 – arr[n-1])

      代码如下所示：

      1. #include <iostream>
      2. #include <stdio.h>
      4. bool isSubsetSum (int arr[], int n, int sum)
      5. {
      6.    // 基本情况
      7.    if (sum == 0)
      8.      return true;
      9.    if (n == 0 && sum != 0)
      10.      return false;
      12.    // 如果最后一个元素比sum大，就不考虑该元素
      13.    if (arr[n-1] > sum)
      14.      return isSubsetSum (arr, n-1, sum);
      16.   //分别判断包括最后一个元素 和 不包括最后一个元素
      17.    return isSubsetSum (arr, n-1, sum) || isSubsetSum (arr, n-1, sum-arr[n-1]);
      18. }
      20. bool findPartiion (int arr[], int n)
      21. {
      22.     int sum = 0;
      23.     for (int i = 0; i < n; i++)
      24.        sum += arr[i];
      26.     // 奇数不可能划分
      27.     if (sum%2 != 0)
      28.        return false;
      30.     return isSubsetSum (arr, n, sum/2);
      31. }
      33. // 测试
      34. int main()
      35. {
      36.   int arr[] = {
      37.        3, 1, 5, 9, 12};
      38.   int n = sizeof(arr)/sizeof(arr[0]);
      39.   if (findPartiion(arr, n) == true)
      40.      printf("Can be divided into two subsets of equal sum");
      41.   else
      42.      printf("Can not be divided into two subsets of equal sum");
      43.   return 0;
      44. }

      时间复杂度：最快情况为 O(2n)，即每个元素有选或不选的两种选择

      动态规划

      如果所有元素的总和sum不是特别大时可以用动态规划来解决。问题可以转化为 是否有子集合的总和为sum/2.
      这里通过自下向上打表的方法来记录子问题的解, part[i][j] 表示对于子集合 {arr[0], arr[1], ..arr[j-1]} 其总和是否为i.

      其实这个问题和01背包问题是一样的。背包的最大容量为sum/2，如果最大价值可以达到sum/2则返回TRUE。

      1. bool findPartiion (int arr[], int n)
      2. {
      3.     int sum = 0;
      4.     int i, j;
      6.     for (i = 0; i < n; i++)
      7.       sum += arr[i];
      9.     if (sum%2 != 0)  
      10.        return false;
      12.     bool part[sum/2+1][n+1];
      14.     for (i = 0; i <= n; i++)
      15.       part[0][i] = true;
      17.     for (i = 1; i <= sum/2; i++)
      18.       part[i][0] = false;     
      20.      for (i = 1; i <= sum/2; i++)  
      21.      {
      22.        for (j = 1; j <= n; j++)  
      23.        {
      24.          part[i][j] = part[i][j-1];
      25.          if (i >= arr[j-1])
      26.            part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
      27.        }        
      28.      }    
      30.     /** //测试打表数据
      31.      for (i = 0; i <= sum/2; i++)  
      32.      {
      33.        for (j = 0; j <= n; j++)  
      34.           printf ("%4d", part[i][j]);
      35.        printf("\n");
      36.      } */
      38.      return part[sum/2][n];
      39. }

      时间复杂度为 O(sum*n)

      二项式系数

      以下是常见的二项式系数的定义:

      • 1) 一个二项式系数C(n,k) 可以被定义为(1+X)n 的展开式中 X**k 的系数。
      • 2) 二项式系数对组合数学很重要，因它的意义是从n件物件中，不分先后地选取k件的方法总数，因此也叫做组合数.

      问题[13]: 写一个函数，它接受两个参数n和k，返回二项式系数C(n,k)。例如，你的函数应该返回6 当n = 4 k = 2时，返回10当 n = 5 k = 2时。

      1) 最优子结构

      C(n,k)的值可以递归地使用以下标准公式计算，这个应该是：
      C(n,k)=C(n−1,k−1)+C(n−1,k)
      C(n,0)=C(n,n)=1

      2) 重叠子问题

      下面是一个直接用上面的公式写的递归程序解决：

      1. // 直接递归实现
      2. #include<stdio.h>
      4. // 返回二项式系数的值 C(n, k)
      5. int binomialCoeff(int n, int k)
      6. {
      7.   // 基本情况
      8.   if (k==0 || k==n)
      9.     return 1;
      11.   // Recur
      12.   return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
      13. }
      15. /* 测试程序 */
      16. int main()
      17. {
      18.     int n = 5, k = 2;
      19.     printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
      20.     return 0;
      21. }

      应该指出的是，上面的程序一次又一次计算相同的子问题。看到下面的递归树n = 5 k = 2。函数C(3,1)执行两次。对于较大的n 值,将会有许多共同的子问题。

      1. C(5,    2)
      2.              /                      \
      3.     C(4, 1)                           C(4, 2)
      4.      /   \                          /           \
      5. C(3, 0)   C(3, 1)             C(3, 1)               C(3, 2)
      6.          /    \               /     \               /     \
      7.   C(2, 0)    C(2, 1)      C(2, 0) C(2, 1)          C(2, 1)  C(2, 2)
      8.             /        \              /   \            /    \
      9.         C(1, 0)  C(1, 1)      C(1, 0)  C(1, 1)   C(1, 0)  C(1, 1)

      很明显，这个问题可以用动态规划来解决，因为包含了动态规划的两个基本属性(见重叠子问题和最优子结构）

      和经典的动态规划解决办法一样，这里通过自下而上的构建数组 C[][] 保存子问题的值。

      1. #include<stdio.h>
      2. int min(int a, int b);
      3. // 返回二项式系数 C(n, k)
      4. int binomialCoeff(int n, int k)
      5. {
      6.     int C[n+1][k+1];
      7.     int i, j;
      9.     // 通过自下而上的方式打表
      10.     for (i = 0; i <= n; i++)
      11.     {
      12.         for (j = 0; j <= min(i, k); j++)
      13.         {
      14.             if (j == 0 || j == i)
      15.                 C[i][j] = 1;
      16.              else
      17.                 C[i][j] = C[i-1][j-1] + C[i-1][j];
      18.         }
      19.     }
      20.     return C[n][k];
      21. }
      22. int min(int a, int b)
      23. {
      24.     return (a<b)? a: b;
      25. }
      27. /* 测试程序*/
      28. int main()
      29. {
      30.     int n = 5, k = 2;
      31.     printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );
      32.     return 0;
      33. }

      时间复杂度: O(n*k)
      空间复杂度: O(n*k)

      其实，空间复杂度可以优化到 O(k). 但是实际应用中，还是直接用二维数组打表使用比较多。

      1. // 空间优化
      2. int binomialCoeff(int n, int k)
      3. {
      4.     int* C = (int*)calloc(k+1, sizeof(int));
      5.     int i, j, res;
      7.     C[0] = 1;
      9.     for(i = 1; i <= n; i++)
      10.     {
      11.         for(j = min(i, k); j > 0; j--)
      12.             C[j] = C[j] + C[j-1];
      13.     }
      14.     res = C[k];  // 在释放内存前存储结果
      15.     free(C); 
      16.     return res;
      17. }

      参考资料

      1. 算法导论CLRS
      2. Optimal substructureFrom Wikipedia, the free encyclopedia .
      3. Floyd–Marshall algorithm From Wikipedia, the free encyclopaedia.
      4. Bellman–Ford algorithmFrom Wikipedia, the free encyclopaedia.
      5. Longest Increasing Subsequence
      6. Longest Common Subsequence
      7. Dyanamic programming :Longset common subsequence
      8. Long palindromic Subsequence
      9. Lucene From Wikipedia, the free encyclopedia
      10. Coin Change from geeksforgeeks
      11. Coin Change from algorithms.com
      12. 0-1 knapsack problem
      13. Binomial coefficient

发表评论

表情：
评论列表 （有 0 条评论，363人围观）

还没有评论，来说两句吧...

相关阅读

    相关 动态规划

    一：概念： 和分冶法相似，不同之处在于前者是把问题划分为互不相交的子问题，而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。 基本步骤： ①：刻画一个最优

    我就是我我就是我/ 0 赞/ 128 阅读

    相关 动态规划

    -------------------- 动态规划的设计思想 动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

    柔情只为你懂柔情只为你懂/ 0 赞/ 364 阅读

    相关 动态规划

    1. 首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段 2. 动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”

    刺骨的言语ヽ痛彻心扉刺骨的言语ヽ痛彻心扉/ 0 赞/ 206 阅读

    相关 动态规划

    首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解

    青旅半醒青旅半醒/ 0 赞/ 408 阅读

    相关 动态规划

    > 给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A=”1A2C3D4B56”，B=”B1D23CA45B6A”，”123456”或者”12C4B6”都是最

    以你之姓@以你之姓@/ 0 赞/ 422 阅读

    相关 动态规划

    基本思想：     动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 区别：     与

    ゞ 浴缸里的玫瑰ゞ 浴缸里的玫瑰/ 0 赞/ 553 阅读

    相关 动态规划

    等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。 适合应用动态规划求解的最优化问题应该具备两个要素： 最优子结构：一个问题的最优解包含

    短命女短命女/ 0 赞/ 447 阅读

    相关 动态规划

     1.题目：最长递增子序列（Longest Increasing Subsequence） 问题描述： > 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 374 阅读