避免重复计算
开一个一维数组 dp ,用于保存已经计算过的结果,其中
dp[n] 记录 F(n) 的结果,并用 dp[n]=-1 表示 F(n) 当前还
没有被计算过。
int dp[maxn];
int F(int n){
if (n==0||n==1) return 1; // 递归边界
if (dp[n]!=-1) return dp[n]; // 已经计算过,直接返回结果,不再
重复计算
else {
dp[n]=F(n-1)+F(n-2); // 计算 F(n) ,并保存至 dp[n]
return dp[n]; // 返回 F(n) 的结果
}
}
记
忆
化
搜
索
时间复杂度 O(2
n
) 降到了
O(n)
第 4 页 / 共 40 页