[ACM_动态规划] 数字三角形(数塔)_递推_记忆化搜索

1、直接用递归函数计算状态转移方程,效率十分低下,可以考虑用递推方法,其实就是“正着推导,逆着计算”
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 1000+5
int n;
int a[maxn][maxn];
int d[maxn][maxn];
int main(){ for(;cin>>n && n;){
memset(d,,sizeof(d));
int i,j; for(i=;i<=n;i++){ //输入
for(j=;j<=i;j++){
cin>>a[i][j];
}
} for(j=;j<=n;j++){ //计算最底层d[][]值
d[n][j]=a[n][j];
} for(i=n-;i>=;i--){ //从下向上计算d[][]值
for(j=;j<=i;j++){
d[i][j]=a[i][j]+max(d[i+][j],d[i+][j+]);
}
}
cout<<d[][]<<'\n';
}
}
2、记忆化搜索虽然也是递归,但同时把计算结果保存在d[][]中,可以保证每个节点只访问一次(不必事先确定各状态计算顺序,但需要记录每个状态是否计算过,本题把d[][]初始为-1,>=0则算过。
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 1000+5
int n;
int a[maxn][maxn];
int d[maxn][maxn];
int D(int i,int j){
if(d[i][j]>=)return d[i][j];
return d[i][j]=a[i][j]+(i==n ? : max(D(i+,j),D(i+,j+))); //记忆化搜索要保存每次计算结果
}
int main(){ for(;cin>>n && n;){
memset(d,-,sizeof(d)); //初始化为-1,也是为记忆化搜索做的标记,当>=0时直接返回d[][];
int i,j; for(i=;i<=n;i++){
for(j=;j<=i;j++){
cin>>a[i][j];
}
}
cout<<D(,)<<'\n';
}
}
上一篇:使用python制作ArcGIS插件(1)工具介绍


下一篇:用户管理 之 Linux 用户管理工具介绍