本文共 2559 字,大约阅读时间需要 8 分钟。
动态规划也是一种分治思想,但与分治算法不同的是,分治算法是把原问题分解为若干子问题,
自顶向下,求解各子问题,合并子问题的解从而得到原问题的解。动态规划也是自顶向下把原问
题分解为若干子问题,不同的是,然后自底向上,先求解最小的子问题,把结果存储在表格中,
在求解大的子问题时,直接从表格中查询小的子问题的解,避免重复计算,从而提高算法效率。
分治法核心思想**:** 从上往下分析问题,大问题可以分解为子问题,子问题中还有更小的子问题
假如你参与了某美女机器人的研发,你在这个项目中要求实现一个统计算法:如果美女机器人
一次可以上 1 级台阶,也可以一次上 2 级台阶。求美女机器人走一个 n 级台阶总共有多少种走法。
比如总共有 5 级台阶,求有多少种走法;由于机器人一次可以走两级台阶,也可以走一级台阶,所以只有
两个情况
机器人最后一次走了两级台阶,问题变成了“走上一个 3 级台阶,有多少种走法?”
机器人最后一步走了一级台阶,问题变成了“走一个 4 级台阶,有多少种走法?
可以得出这样的关系(n 表示 一共有多少台阶)
f(n) = f(n-1) + f(n-2);
终止条件 n== 1 时 1种走法;n == 2 时 2种走法;
这样会有很多重复的代码
比如:f(5) = f(4) + f(3)
计算分成两个分支:
f(4) = f(3)+f(2) = f(2) + f(1) + f(2);
f(3) = f(2) + f(1);
f(2) 和 f(1)就是重复计算
自底向上
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3 (状态转移方程)
f(4) = f(3) + f(2) = 3 + 2 = 5
f(5) = f(4) + f(3) = 5 + 3 = 8
这样就可以避免重复计算
效率提高
#include#include using namespace std;/******************************函数功能: 用分治法解决上述问题*函数参数: n - 台阶数**函数返回值: 总共有多少种走法。**************************/int recursionMethod(int n) { if (n <= 0) return 0; if (n == 1) return 1; if (n == 2) return 2; return recursionMethod(n - 1) + recursionMethod(n - 2);}int main(void) { //机器人走台阶 time_t start = 0; time_t end = 0; int n; cout << "please input step:"; cin >> n; //用递归实现 //递归方法 time(&start); int ret = recursionMethod(n); cout << "一共有:" << ret << "种" << endl; time(&end); cout << "递归所需时间:" << end - start << endl; return 0;}
台阶数是40时 所需时间是7秒
如果要求一个问题的最优解(通常是最大值或者最小值),而且该问题能够分解成若干个子问题,
并且小问题之间也存在重叠的子问题,则考虑采用动态规划,注可以使用动态规划算法的都可以使用分治法,但可以使用分治法的不一定可以使用动态规划算法.
五步曲解决:
\1. 判题题意是否为找出一个问题的最优解
\2. 从上往下分析问题,大问题可以分解为子问题,子问题中还有更小的子问题
\3. 从下往上分析问题 ,找出这些问题之间的关联(状态转移方程)
\4. 讨论底层的边界问题
\5. 解决问题(通常使用数组进行迭代求出最优解)
#include#include using namespace std;/******************************函数功能: 用动态规划算法解决上述问题*函数参数: n - 台阶数**函数返回值: 总共有多少种走法。**************************/int dynamicPrograming(int n) { if (n == 1) return 1; if (n == 2) return 2; int* dynamicArr = new int[n]; dynamicArr[0] = 1; //一个台阶时 1种走法 dynamicArr[1] = 2; //2个台阶时 2种走法 for (int i = 2; i < n; i++) { dynamicArr[i] = dynamicArr[i - 1] + dynamicArr[i - 2]; } int ret = dynamicArr[n - 1]; //n个台阶时的走法 delete[] dynamicArr; return ret;}int main(void) { //机器人走台阶 time_t start = 0; time_t end = 0; int n; cout << "please input step:"; cin >> n; time(&start); //用动态规划算法实现 int kind = dynamicPrograming(n); cout << "一共有:" << kind << "种" << endl; time(&end); cout << "动态规划算法所需时间:" << end - start << endl; return 0;}
台阶数是40时 所需时间是0秒
转载地址:http://dbyki.baihongyu.com/