問題描述
有一個由非負(fù)整數(shù)組成的三角形，第一行只有一個數(shù)担映，除了最下行之外每個數(shù)的左下方和右下方各有一個數(shù)废士，如下圖。從第一行的數(shù)開始蝇完，每次可以往左下或右下走一格官硝，直到走到最下行，把沿途經(jīng)過的數(shù)全部加起來短蜕。如何走才能使得這個和盡量大氢架，輸出最大和。
如：
這是一個數(shù)字三角形問題朋魔，可以用記憶化搜索岖研，也可以用遞推。
首先由題意可以得到狀態(tài)轉(zhuǎn)移方程：d[i][j] = tri[i][j] + max(d[i + 1][j], d[i + 1][j + 1]);d[i][j] 為從 tri[i][j] 出發(fā)時（包括 tri[i][j]）能得到的最大和警检。
記憶化搜索
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 100 + 5;
int d[MAX_N][MAX_N];
int tri[MAX_N][MAX_N];//三角形的值
int n;
int solve(int i, int j) {
if (d[i][j] >= 0) return d[i][j];
return d[i][j] = tri[i][j] + (i == n - 1 ? 0 : max(solve(i + 1, j), solve(i + 1, j + 1)));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
memset(d, -1, sizeof(d));//為了防止某個值被重復(fù)計算
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j)
cin >> tri[i][j];
}
solve(0, 0);
cout << d[0][0] << endl;
}```
**遞推**
include <iostream>
include <algorithm>
using namespace std;
const int MAX_N = 100 + 5;
int d[MAX_N][MAX_N];
int tri[MAX_N][MAX_N];//簡單一點可以不要這個數(shù)字孙援，此處為了說明問題
void solve(int n) {
for (int j = 0; j <= n - 1; ++j)
d[n - 1][j] = tri[n - 1][j];//不寫tri[i][j]時，就不需要這一步了
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j)
d[i][j] = tri[i][j] + max(d[i + 1][j], d[i + 1][j + 1]);
//d[i][j] += max(d[i + 1][j], d[i + 1][j + 1]);//不用tri[i][j]時
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j)
cin >> tri[i][j];//cin >> d[i][j];
}
solve(n);
cout << d[0][0] << endl;
}```
這兩種方法的時間復(fù)雜度都是o(n * n)扇雕。用遞推計算的時候需要注意邊界問題和計算順序拓售。采用記憶化搜索時，不必事先確定各狀態(tài)的計算順序镶奉，但需要記錄每個狀態(tài)“是否已經(jīng)計算過”础淤。
