動態規劃——數塔問題

從數塔頂層出發，每個結點可以選擇向左走或向右走，要求一直走到塔底，使得走過的路徑上的數值和最大。

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100;
// 下麵這個函數實現的是更新最大值，o賦值為o和x的最大值
template <class T>
void updateMax(T& o, const T& x) {
    o = (o > x) ? o : x;
}

// f數組為動態規劃的狀態數組
// num數組為讀入的數塔
// n為讀入的數塔高度
int f[N][N], num[N][N], n;

int main() {
    // 讀入n和數塔數組num
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            scanf("%d", &num[i][j]);
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            //從上到下 用另一個數組儲存走到當前最大的值
            updateMax(f[i][j],max(f[i - 1][j],f[i - 1][j - 1])+num[i][j]);
        }
    }// step 1 begin: 在這裡實現動態規划算法邏輯
    
    // step 1 end.

    // 定義最終結果變數result，因為是計算最大值，所以初始化為0
    int result = 0;
    for (int i = 1; i <= n; ++i) {//因為上一個迴圈已經計算了值 所以可以直接在最後一層查找
        // step 2 begin: 在這裡實現更新最終結果的邏輯
        updateMax(result,f[n][i]);//是賦值而不是交換 記住啦！！！！！！
        // step 2 end.
    }
    // 輸出最終最大權值和result
    printf("%d\n", result);
    return 0;
}