題目描述
在一座山上,有很多很多珠寶,它們散落在山底通往山頂?shù)拿織l道路上,不同道路上的珠寶的數(shù)目也各不相同.下圖為一張藏寶地圖:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

”奪寶奇兵”從山下出發(fā),到達山頂,如何選路才能得到最多的珠寶呢?在上圖所示例子中,按照5-> 7-> 8-> 3-> 7的順序,將得到最大值30
輸入
第一行正整數(shù)N(100> =N> 1),表示山的高度
接下來有N行非負整數(shù),第i行有i個整數(shù)(1< =i< =N),表示山的第i層上從左到右每條路上的珠寶數(shù)目
輸出
一個整數(shù),表示從山底到山頂?shù)乃艿玫降闹閷毜淖畲髷?shù)目.
樣例輸入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

樣例輸出

30

首先，我們直接從上往下dfs。

代碼如下：

#include <iostream> using namespace std; const int N = 110; int mp[N][N]; int dp[N][N]; int n;int dfs(int x, int y) {if (x == n)return mp[x][y];return dp[x][y] = max(dfs(x + 1, y), dfs(x + 1, y + 1)) + mp[x][y]; }int main() {cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> mp[i][j];dfs(1, 1);cout << dp[1][1] << endl;return 0; }

可以看到超時，而且時間是2358

現(xiàn)在我們記憶化搜索。

代碼如下：

#include <iostream> #include <cstring> using namespace std; const int N = 110; int mp[N][N]; int dp[N][N]; int n;int dfs(int x, int y) {if (x == n)return mp[x][y];if (dp[x][y] >= 0)//實現(xiàn)記憶化搜索return dp[x][y];return dp[x][y] = max(dfs(x + 1, y), dfs(x + 1, y + 1)) + mp[x][y]; }int main() {cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> mp[i][j];memset(dp, -1, sizeof(dp));dfs(1, 1);cout << dp[1][1] << endl;return 0; }

時間變成了1。

用dp的話，時間為2，比記憶化搜索慢一點。

[藍橋杯][算法提高VIP]奪寶奇兵-dp

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]夺宝奇兵-递推+记忆化搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。