数字记忆递归算法实现数塔问题 c++
时间: 2023-08-02 12:09:10 浏览: 58
以下是使用 C++ 实现的数塔问题的递归算法,采用数字记忆的方式来避免重复计算:
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> tower = {{9},
{12, 15},
{10, 6, 8},
{2, 18, 9, 5},
{19, 7, 10, 4, 16}};
vector<vector<int>> memory(5, vector<int>(5, -1));
int max_sum(int i, int j) {
if (i == 4) {
return tower[i][j];
}
if (memory[i][j] != -1) {
return memory[i][j];
}
int left = max_sum(i+1, j);
int right = max_sum(i+1, j+1);
int result = tower[i][j] + max(left, right);
memory[i][j] = result;
return result;
}
int main() {
cout << max_sum(0, 0) << endl;
return 0;
}
```
输出结果为 55,即从第一层第一个数字出发能够得到的最大和。