算法学习之动态规划详解

定义

动态规划与贪心法类似，但不同的是动态规划是讲究整体最优解，它的当前步做出的最优解与之前的每一步的状态有关，而贪心法当前步得出的最优解只与上一步的状态有关。动态规划主要难在模型的建立。 ## 解题步骤

找出最优解性质，刻画其结构特征和最优子结构特征

递归的定义最优值，刻画原问题与子问题解间的关系

自底向上的计算各个子问题、原问题的最优值，并避免子问题的重复计算

根据计算最优值得到的信息，构造最优解

例1：金字塔求和问题

给定一个由n行数字组成的数字三角型，如图所示。设计一个算法，计算从三角形的顶至底的一条路径，使该路径经过的数字总和最大。路径上的每一步都只能往左下或右下走，给出这个最大和。 7 3 8 8 1 0

2 7 4 4 4 5 2 6 5

方法一：正向思考，第k步到第k+1步，比较第k步中的数据，找出到达第k+1步的k+1个次优解，然后到第n步一共有n个次优路径可走，然后从中比较出最大的

#include<cstring> #include<iostream> #include<algorithm> using namespace std; int main(){ int sum[100][100] ;//每走一步所有情况的总和 int t[100][100] ;//输入的三角形存放的数据 memset(sum, 0, sizeof(sum));//cstring中的库函数，初始化每个数据为0 memset(t, 0, sizeof(t)); int n;//行数 cout << "请输入行数：" << endl; cin >> n; cout << "请按三角形形状输入数据:" << endl; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cin >> t[i][j]; } } sum[1][1] = t[1][1]; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { if (j == 1 ) { sum[i][j] = sum[i - 1][j] + t[i][j]; } else if (j == i) { sum[i][j] = sum[i - 1][j - 1] + t[i][j]; } else { sum[i][j] = max(sum[i - 1][j - 1], sum[i][j - 1]) + t[i][j];//algorithm中的库函数max } } } int max=0;//最大的和 for (int j = 1; j <= n; j++) { if (sum[n][j] > max) max = sum[n][j]; } cout << "最大的和为" << max; }

方法二：逆向思考 从下到上，逆向思维，最终的一条路径即为最优路径

#include<iostream> #include<cstring> #include<algorithm> using namespace std; int main() { int sum[100][100];//每走一步所有情况的总和 int t[100][100];//输入的三角形存放的数据 memset(sum, 0, sizeof(sum));//cstring中的库函数，初始化每个数据为0 memset(t, 0, sizeof(t)); int n;//行数 cout << "请输入行数：" << endl; cin >> n; cout << "请按三角形形状输入数据:" << endl; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cin >> t[i][j]; } } for (int j = 1; j <= n; j++) { sum[n][j] = t[n][j]; } for (int i = n-1; i > 0; i--) { for (int j = 1; j <= i; j++) { sum[i][j] = max(sum[i + 1][j], sum[i + 1][j+1]) + t[i][j]; } } cout <<"最大的和为"<< sum[1][1]; }

例2：最长递增子序列

#include<iostream> #include<cstring> #include<algorithm> using namespace std; int main() { int a[100]; memset(a, 0, sizeof(a)); int n; cout << "请输入数的个数" << endl; cin >> n;; cout << "请输入数据：" << endl; for (int i = 0; i < n; i++) { cin >> a[i]; } int d[100];//以输入的每个数据为结尾的最长递增子序列的个数 memset(d, 0, sizeof(d)); for (int i = 0; i < n; i++) { d[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i]) { d[i] = max(d[i], d[j] + 1);//实际上是一种正向递归 } } } int max = d[0]; for (int i = 1; i < n; i++) { if (d[i] > max) { max = d[i]; } } cout << max << endl; }