/
githubmirror
/
hello-algo
Обзор
Документация
Войти
/
githubmirror
/
hello-algo
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
main
codes/cpp/chapter_dynamic_programming/climbing_stairs_dfs_mem.cpp
39 строк
909 B
Yudong Jin
Some improvements (#1073)
07 фев 2024, 17:21
Не верифицирован
07 фев 2024, 17:21
a005c6e
Код
Авторство
О чём код?
/** * File: climbing_stairs_dfs_mem.cpp * Created Time: 2023-06-30 * Author: krahets (krahets@163.com) */ #include "../utils/common.hpp" /* 记忆化搜索 */ int dfs(int i, vector<int> &mem) { // 已知 dp[1] 和 dp[2] ，返回之 if (i == 1 || i == 2) return i; // 若存在记录 dp[i] ，则直接返回之 if (mem[i] != -1) return mem[i]; // dp[i] = dp[i-1] + dp[i-2] int count = dfs(i - 1, mem) + dfs(i - 2, mem); // 记录 dp[i] mem[i] = count; return count; } /* 爬楼梯：记忆化搜索 */ int climbingStairsDFSMem(int n) { // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录 vector<int> mem(n + 1, -1); return dfs(n, mem); } /* Driver Code */ int main() { int n = 9; int res = climbingStairsDFSMem(n); cout << "爬 " << n << " 阶楼梯共有 " << res << " 种方案" << endl; return 0; }