为什么一个输入数据记忆化能优化时间复杂度?

P1255 数楼梯

_SGH_ @ 2024-12-01 09:46:39

记忆化的代码

include <bits/stdc++.h>
using namespace std;
long long shao[55];
long long ss(int m){
    if(shao[m]!=0) return shao[m];
    if(m == 1){
        return 1;
    }
    if(m == 2){
        return 2;
    }
    shao[m]= ss(m-1)+ss(m-2);
    return shao[m]; 
}
int main(){
    int n;
    cin >> n;
    cout << ss(n);

    return 0;
} ``````
没记忆化的:
```cpp
#include <bits/stdc++.h>
using namespace std;
long long shao[55];
long long ss(int m){
    if(m == 1){
        return 1;
    }
    if(m == 2){
        return 2;
    }
    return ss(m-1)+ss(m-2); 
}
int main(){
    int n;
    cin >> n;
    cout << ss(n);

    return 0;
}

by niuniudundun @ 2024-12-01 09:53:55

@SGH数组开大点?


by niuniudundun @ 2024-12-01 09:55:08

@SGH用高精。


by shawn0618 @ 2024-12-01 09:57:58

不明白什么叫“输入数据记忆化”。

@SGH


by _SGH_ @ 2024-12-01 10:05:04

@niuniudundun没准备用高精呐,就是想试一下递归(学记忆化)


by _SGH_ @ 2024-12-01 10:22:32

@shawn0618大佬能不能解释一下


by shawn0618 @ 2024-12-01 10:31:33

如果是普通的记忆化的话。

把算过的记下来,可以节省重复算的时间。

正常的话可以拿60分。


by shawn0618 @ 2024-12-01 10:44:18

测过了没问题,不开高精是拿不到后面的40分的。

我们假设存在一个数组,下表从1开始,如果使用记忆化的话。 0 0 0 0 0

假设要计算结果为5的答案,会递归ss(4)ss(3)

计算ss(4),会递归ss(3)ss(2).

计算ss(3),会递归ss(2)ss(1),此时ss(2)ss(1)会计算出2和1,回到ss(3),并在数组中记录下来2和1,以免重复计算。 1 2 0 0 0

接下来计算ss(2),由于数组已经记录了下表为2的答案,所以可以直接得到结果2。

以此类推,直到执行完栈。

数组变为: 1 2 3 5 8

执行到这一步时,访问return shao[m]; ,得到答案8。

@SGH


by _SGH_ @ 2024-12-01 11:19:43

@shawn0618蟹蟹大佬,懂了!


|