演算法思路：將每一個位置的三角形數字更新為該數字下面或右下方的最大數字之和，最后得到的陣列的值就是三角形路徑的最大值
DFS暴搜
沿著一個路徑搜索到底，在回溯的路上遇到能走的路徑就繼續進行搜索，并且已經計算出來的值不用在進行搜索，直接回傳，重復搜索的話會導致超時，
大概的搜索如上圖所示
代碼：
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int f[N][N];
int ans[N][N];
int n;
int dfs(int i, int j){
if(i == n) return f[i][j];//遞回結束條件，如果搜索到了底層就直接回傳呼層的值（邊界）
if(ans[i][j]) return ans[i][j]; //如果被搜索過了就直接回傳利用該值即可，不用重復搜索
return ans[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + f[i][j];//每次更新值，去下面和右下方的值進行更新，取最大
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++ )
for(int j = 0; j <= i; j ++ )
scanf("%d", &f[i][j]);
printf("%d\n", dfs(0, 0));
return 0;
}
DP
從下往上求最大不存在邊界問題
#include<iostream>
using namespace std;
const int N = 10010;
int f[N][N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
scanf("%d", &f[i][j]);
for (int i = n - 1; i >= 0; i--)
for (int j = i; j >= 0; j--)
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j];
printf("%d\n", f[0][0]);
return 0;
}
操作程序：
第一次：
1
2 3
4 5 6
7 8 9 10
第二次：
1
2 3
12 14 16
第三次：
1
16 19
第四次：
20
每次從更新一行，改行的數字都更新為該數字和該數字下方或右下方的最大數字之和，每一行都這么作，那么到第一行的那一個數字一定是最大值
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277763.html
標籤：其他
上一篇：人機互動——互動技術
下一篇：JAVA初窺-DAY13