用递归求解问题时，反复的嵌套会浪费内存。而且更重要的一点是，之前计算的结果无法有效存储，下一次碰到同一个问题时还需要再计算一次。例如递归求解 Fibonacci 数列，假设求第 n 位（从 1 开始）的值，C 代码如下：

#include <stdio.h> int fib(int n) { if (n < 3) { return 1; } return fib(n - 1) + fib(n - 2); } int main(void) { int ret = fib(5); printf("fib ret is: %d\n", ret); return 0; }

上面的代码，每个运算节点都需要拆成两步运算，时间复杂度位 O(2^n)。

你可以把 n 改为 40 左右试试，这是消耗的时间就是秒级了。总共的求解步骤如下：

求第 5 位 求第 4 位 求第 3 位 求第 2 位求第 1 位求第 2 位求第 3 位 求第 2 位求第 1 位

如果想把每次求解的结果保存下来，就需要一个长度位 n 的数组，从头开始把每一个位置的值保存下来，这样求解后面的值的时候就可以用了。

动态规划（Dynamic Programming）的思想

对于递归，只要写好了退出条件，之后不停的调用自身即可，最终到达退出条件时，逐个退出函数。

动态规划则是从头开始，用循环达到目的。

动态规划和递归的最大的区别，就是在碰到重叠子问题（Overlap Sub-problem）时，是否只需要计算一次。

#include <stdio.h> int fib(int n) { int i; int dp_opt[n]; dp_opt[0] = 1; dp_opt[1] = 1; for (i = 2; i < n; i++) { dp_opt[i] = dp_opt[i - 1] + dp_opt[i - 2]; } return dp_opt[n - 1]; } int main(void) { int ret = fib(5); printf("fib ret is: %d\n", ret); return 0; }

上面代码的时间复杂的是 O(n)。

示例

求任意 n 个非相邻数字之和

题目：从集合中，任取任意多个非相邻的数字并求和，找出最大的和。例如，对于 {1， 9， 2， 5， 4}，最大的和是 14。

分析：对于任意第 n 位数字，都有两种情况，只需要取值最大的那种即可：

选中，则该元素的最大和为：当前元素值加上第 n - 2 位的最大和，即 OPT(n) = OPT(n - 2) + arr[n]不选，则该元素的最大和为：第 n - 1 位的最大和，即 OPT(n) = OPT(n - 1)

递归解法

递归退出条件：

当计算到第一个元素时，直接返回这个元素的值当计算到第二个元素时，返回前两个元素中的最大值

递归循环：

递归计算当前元素的最大和递归计算前一个元素的最大和返回这两个最大和中的大者 int recursive(int arr[], int n, int i) { if (i == 0) return arr[0]; if (i == 1) return arr[0] > arr[1] ? arr[0] : arr[1]; int before = recursive(arr, n, i - 2) + arr[i]; int cur = recursive(arr, n, i - 1); return cur > before ? cur : before; }

动态规划

为了确保每个最小子问题都只计算一次，就必须把计算的结果保存起来。另外，跟递归的逆序求解方向相反，动态规划从第一个元素开始，依次计算每个元素的最大和：

创建跟待求解问题同规模的数组 dp_opt，用来存放每个元素的最大和计算第一个元素的最大和（即这个元素的值），并放入 dp_opt 的第一个位置计算第二个元素的最大和（即前两个元素的最大值），并放入 dp_opt 的第二个位置从第三个位置开始，循环到最后一个位置，循环内容为： 计算当前位置的前一个位置对应的最大和 x计算当前位置元素 arr[n] 加上前前一个位置对应的最大和 ydp_opt[n] = max(x, y + arr[n]) int dp_opt(int arr[], int n, int x) { int i; int before, cur; int opt[n]; for (i = 0; i < n; i++) { opt[i] = 0; } opt[0] = arr[0]; opt[1] = arr[0] > arr[1] ? arr[0] : arr[1]; for (i = 2; i < n; i++) { before = opt[i - 2] + arr[i]; cur = opt[i - 1]; opt[i] = cur > before ? cur : before; } return opt[x]; }

综合示例

#include <stdio.h> // 递归解法 int recursive(int arr[], int n, int i) { if (i == 0) return arr[0]; if (i == 1) return arr[0] > arr[1] ? arr[0] : arr[1]; int before = recursive(arr, n, i - 2) + arr[i]; int cur = recursive(arr, n, i - 1); return cur > before ? cur : before; } // 动态规划 int dp_opt(int arr[], int n, int x) { int i; int before, cur; int opt[n]; for (i = 0; i < n; i++) { opt[i] = 0; } opt[0] = arr[0]; opt[1] = arr[0] > arr[1] ? arr[0] : arr[1]; for (i = 2; i < n; i++) { before = opt[i - 2] + arr[i]; cur = opt[i - 1]; opt[i] = cur > before ? cur : before; } return opt[x]; } int main() { int i; int n = 7; int arr[] = {1, 2, 4, 1, 7, 8, 3}; for (i = 0; i < 7; i++) { printf("recursive ret is: %d, dp_opt ret is: %d\n", recursive(arr, n, i), dp_opt(arr, n, i)); } return 0; }

已知某个值，判断在正数集合中是否存在元素的组合，刚好组合中的元素之和等于这个值

例如，对于 {2, 5, 8, 22, 9}，给定值位 15，则可以找到组合 {2, 5, 8} 满足条件。

要判断多个元素之和是否等于某个值 sum，则对于任意的元素 n，情况如下：

选择，此时需要判断前 n - 1 个元素之和能否等于 (sum - arr[n])不选，此时需要判断前 n - 1 个元素之和能否等于 sum

递归的思路

递归退出条件：

找到第一个元素了，则将这个元素的值和 s 比较，并返回 true 或 falsesum < 0，说明第 n 个元素太大，需要剔除，跳到 recursive(arr, n - 1, sum)sum = 0，说明第 n 个元素就是所求组合中的最后一个元素，返回 true

递归循环：

将 sum 减去当前元素，然后作为和，递归计算前一个元素判断上面的返回值，如果是 true，则直接结束递归，返回 true用 sum 递归计算前一个元素，并直接返回结果 int recursive(int arr[], int n, int sum) { if (n == 0) return arr[0] == sum; if (sum == 0) return 1; if (sum < arr[n]) return recursive(arr, n - 1, sum); return recursive(arr, n - 1, sum) || recursive(arr, n - 1, sum - arr[n]); }

动态规划的思路

有了上面的递归的思路后，再把递归转为动态规划。

初始化二维数组

上一个例子中，求非相邻元素最大和时，每个元素的位置上只需要保存当前元素的最大值，所以创建一个一维数组即可。而现在已知元素之和，

例如，对于集合 {3, 5, 9, 1, 2}，如果 sum = 6，则需要创建 dp_subset[5][7] 数组：

对于第一行，因为第一个元素是 3，所以其只可能等于 3（对应递归退出条件 if (i == 0) return arr[0] == sum;）对于第一列，全部为 True（对应递归退出条件 if (sum == 0) return true;） arr[i]i \ sum012345630FFFTFFF50T90T10T20T

开始迭代

在已经初始化的二维数组基础上，参考递归体就可以完成迭代的代码。另外，还有一个递归结束条件也放在迭代里面。

创建一个二重循环，从第二行二列开始遍历数组如果 arr[i] > sum（递归结束条件），则 dp_subset[i][s] = dp_subset[i - 1][s]（对应 if (arr[i] > sum) recursive(arr, n - 1， sum);否则，判断 dp_subset[i - 1][s] 和 dp_subset[i - 1][s - arr[i]]，只要有一个是 true，就把 dp_subset[i][s] 置为 true int dp_subset(int arr[], int n,

完整示例

#include <stdio.h> // 递归解法 int recursive(int arr[], int n, int sum) { if (n == 0) return arr[0] == sum; if (sum == 0) return 1; if (sum < arr[n]) return recursive(arr, n - 1, sum); return recursive(arr, n - 1, sum) || recursive(arr, n - 1, sum - arr[n]); } // 动态规划 int dp_subset(int arr[], int n, int sum) { int subset[n][sum + 1]; int i, s; for (i = 0; i < n; i++) { for (s = 0; s <= sum; s++) subset[i][s] = 0; } for (i = 0; i < n; i++) { subset[i][0] = 1; } subset[0][0] = 0; subset[0][arr[0]] = 1; for (i = 1; i < n; i++) { for (s = 1; s <= sum; s++) { if (arr[i] > sum) { subset[i][s] = subset[i - 1][s]; } else { subset[i][s] = subset[i - 1][s] || subset[i - 1][s - arr[i]]; } } } return subset[n - 1][sum]; } int main() { int n = 7; int arr[] = {1, 2, 4, 7, 8, 3, 32}; int sum = 3; printf("recursive ret is: %d, dp_opt ret is: %d\n", recursive(arr, n, sum), dp_subset(arr, n, sum)); return 0; }

转载于:https://www.cnblogs.com/kika/p/10851492.html