算法笔记 11.1 动态规划的递归写法和递推写法
动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。将一个复杂的问题分解成若干子问题,通过综合子问题的最优解来得到原问题的最优解。注意:dp会将每个求解过的子问题的解记录下来,下次遇到同样的问题时,就可以直接使用之前的记录的结果而不是重复计算。
1.动态规划的递归写法(记忆化搜索) 自顶向下
记录子问题的解,来避免下次遇到相同子问题时重复计算
递归求斐波那契数列O(2^n)
int F(int n){
if(n==0||n==1) return 1;
return F(n-1)+F(n-2);
}
O(n)
int dp[100]={0};
int F(int n){
if(n==0||n==1) return 1;
if(dp[n]!=0) return dp[n];
else{
dp[n]=F(n-1)+F(n-2);
return dp[n];
}
}
如果一个问题可以被分为若干个子问题,且这些子问题会重复出现,那么就称这个问题拥有重叠子问题,只有拥有重叠子问题的问题才能用dp来解
2.动态规划的递推写法 自底向上
数塔问题:
f[i][j]存储第i行第j个点的数值,令dp[i][j]表示第i行第j个数字出发的到达最底层的所有路径中能得到的最大和。i,j都从1开始
显然: dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j]
得到状态转移方程,而最后一层dp值总是等于元素本身。
即:dp[n][j]==f[n][j](1<=j<=n) 把这种可以直接确定其结果的部分称为边界
而动规的递推写法总是从这些边界出发,通过状态转移方程扩散到整个dp数组。
从最底层各位置的dp值开始,不断往上求出每一层各位置的dp值,最后就会得到最终结果dp[1][1]
#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
const int N=1000;
int f[N][N],dp[N][N];
int main(){
// freopen("input.txt","r",stdin);
int n;
while(cin>>n){
//录入数塔
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>f[i][j];
}
}
//录入边界
for(int j=1;j<=n;j++){
dp[n][j]=f[n][j];
}
//状态转移 从n-1层不断往上计算出dp[i][j]
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
//每次通过i+1层求第i层 且每次i+1都先求出来了
}
}
cout<<dp[1][1]<<endl;
}
return 0;
}
递归写法自顶向下,递推写法自底向上