动态规划
-
数字三角形
用递归实现，复杂度为
# include<iostream> //max函数在algorithm头文件里 # include<algorithm> using namespace std; #define MAX 101; int N; int D[MAX][MAX]; int maxSum(int i,int j){ if(i == N) return D[i][j]; else{ return max(maxSum(i+1,j),maxSum(i+1,j+1])+D[i][j]; } } int main(){ cin >> N; for(int i = 0;i<N;i++){ for(int j = 0;j<=i;j++){ cin >> D[i][j]; } } cout << maxSum(0,0); } -
使用动态规划来做
#include<iostream> #include<algorithm> #define MAX 101 using namespace std; int N; int D[MAX][MAX]; //一个记录中间运算结果的数组 int maxSum[MAX][MAX]; int MaxSum(int i,int j){ //如果已经算过一次，无需再次计算,避免了重复计算降低复杂度 if(maxSum[i][j] != -1) return maxSum[i][j]; //如果为最后一行，D[i][j]的值就是maxSum[i][j]的值 if(i==N) maxSum[i][j] = D[i][j]; else{ maxSum[i][j] = max(MaxSum(i+1,j),MaxSum(i+1,j+1))+D[i][j]; } return maxSum[i][j]; } int main(){ cin >> N; for(int i = 0;i<N;i++){ for(int j = 0;j<= i;j++){ cin >> D[i][j]; //给存储中间数据的数组赋一个不可能的初值 maxSum[i][j] = -1; } } cout << MaxSum(0,0); }因为递归要用到函数调用，我们可以直接用递推做，不用调用函数，提高效率
而且递归可能存在递归深度太大，堆栈不够用的情况
#include<iostream>
#include<algorithm>
#define MAX 100
using namespace std;
int N;
int D[MAX][MAX];
int maxSum[MAX][MAX];
int main(){
cin >> N;
for(int i = 0;i<N;i++){
for(int j = 0;j<=i;j++){
cin >> D[i][j];
}
}
//边界值——最后一行是确定的
for(int j = 0;j<N;j++){
maxSum[N][j] == D[N][j];
}
//往上递推
for(int i = n-1;i>=0;i--){
for(int j = 0;j<=i;j++){
maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
}
}
cout << maxSum[0][0];
}
进一步，可以进行空间优化，使用以为数组存储maxSum，因为里面的数是滚动更新的；
这也体现了递推的一个优势——有时候可以使用滚动数组
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;
int D[MAX][MAX];
int n;
int main(){
cin >> n;
for(int i = 0;i<n;i++){
for(int j = 0;j<=i;j++){
cin >> D[i][j];
}
}
int * sumMax;
//建立一个指针指向D[n]，把递推的过程变成更新D[n]中的数
sumMax = D[n];
for(int i = n-1;i>=0;i--){
for(int j = 0;j<=i;j++){
sumMax[j] = max(sumMax[j],sumMax[j+1]) + D[i][j];
}
}
cout << sumMax[0];
}
-
最长上升子序列问题
#include <iostream> #include <algorithm> #define MAX 1000 using namespace std; int a[MAX]; //建立 一个数组来存放每一个状态 int maxLen[MAX]; int n; int main(){ cin >> n; for(int i = 0;i<n;i++){ cin >> a[i]; maxLen[i] = 1; } for(int i = 1;i<n;i++){ for(int j = 0;j<i;j++){ //maxLen[]是不断更新的，max函数控制是否要更新maxLen if(a[i]>a[j]) maxLen[i] = max(maxLen[i],maxLen[j]+1); } } //输出maxLen[]（容器）中最大的一个,第一个参数为起始，左闭右开；在头文件algorithm中 cout << * max_element(maxLen,maxLen+n); }- 最长子串问题
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 1000
using namespace std;
char str1[MAX];
char str2[MAX];
//有两个
int maxLen[MAX][MAX];
int main(){
while (cin >> str1 >> str2)
{
int lenth1 = strlen(str1);
int lenth2 = strlen(str2);
int nTmp;
int i,j;
//先确定边界状态
for(i = 0;i < lenth1;i++){
maxLen[i][0] = 0;
}
for(j = 0;j < lenth2;j++){
maxLen[0][j] = 0;
}
//递推式,这里是难点
for(int i = 1;i<lenth1;i++){
for(int j = 1;j<lenth2;j++){
//这里如果不用i-1第一个字母相同不会记录
if(str1[i-1] == str2[j-1]){
maxLen[i][j] = maxLen[i-1][j-1] +1;
}else{
//证明，maxLen[i][j]不小于其中的任何一个也不大于其中的任何一个
maxLen[i][j] = max(maxLen[i-1][j],maxLen[i][j-1]);
}
}
}
cout << maxLen[lenth1-1][lenth2-1] << endl;
}
return 0;
}
-
动态规划问题最难的地方是
设计状态，找到状态转移的递推关系式
设计状态的原则：
是原问题子问题的解
具有最有子结构（原问题的最优解所包含的子问题，解也是最优的）
无后效性（只跟当前状态有关，而与怎么抵达这个状态无关）
