使用C++语言完成文件里的数字三角问题

好的，下面是使用C++语言完成“数字三角问题”的代码实现。我们将分别使用普通的动态规划法和备忘录法来解决这个问题。

### 普通动态规划法

#include <iostream>
using namespace std;

const int N = 5;
int number[N][N] = {
    {7},
    {3, 8},
    {8, 1, 0},
    {2, 7, 4, 4},
    {4, 5, 2, 6, 5}
};

void printPath(int path[N][N], int row, int col) {
    for (int i = 0; i <= row; ++i) {
        cout << number[i][path[row][col]] << " ";
        col = path[row][col];
        --row;
    }
    cout << endl;
}

int main() {
    int dp[N][N];
    int path[N][N];

    // Initialize the last row of dp and path
    for (int i = 0; i < N; ++i) {
        dp[N-1][i] = number[N-1][i];
        path[N-1][i] = -1; // No further steps from the bottom
    }

    // Fill the dp table from bottom to top
    for (int i = N - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            if (dp[i + 1][j] > dp[i + 1][j + 1]) {
                dp[i][j] = number[i][j] + dp[i + 1][j];
                path[i][j] = j;
            } else {
                dp[i][j] = number[i][j] + dp[i + 1][j + 1];
                path[i][j] = j + 1;
            }
        }
    }

    // Find the maximum sum and its path
    int maxSum = dp[0][0];
    int maxIndex = 0;
    for (int i = 1; i < N; ++i) {
        if (dp[0][i] > maxSum) {
            maxSum = dp[0][i];
            maxIndex = i;
        }
    }

    cout << "Maximum sum: " << maxSum << endl;
    cout << "Path: ";
    printPath(path, 0, maxIndex);

    return 0;
}

### 备忘录法

#include <iostream>
#include <vector>
using namespace std;

const int N = 5;
int number[N][N] = {
    {7},
    {3, 8},
    {8, 1, 0},
    {2, 7, 4, 4},
    {4, 5, 2, 6, 5}
};

vector<int> path;

int memo[N][N];

int dfs(int row, int col) {
    if (row == N - 1) {
        return number[row][col];
    }

    if (memo[row][col] != -1) {
        return memo[row][col];
    }

    int left = dfs(row + 1, col);
    int right = dfs(row + 1, col + 1);

    if (left > right) {
        path.push_back(number[row][col]);
        return memo[row][col] = number[row][col] + left;
    } else {
        path.push_back(number[row][col]);
        return memo[row][col] = number[row][col] + right;
    }
}

int main() {
    // Initialize memoization table with -1
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            memo[i][j] = -1;
        }
    }

    int maxSum = dfs(0, 0);

    cout << "Maximum sum: " << maxSum << endl;
    cout << "Path: ";
    for (auto it = path.rbegin(); it != path.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

### 解释

1. **普通动态规划法**:
- 我们使用一个二维数组 `dp` 来存储从当前节点到底部的最大路径和。
- 另外一个二维数组 `path` 用于记录路径。
- 从底部向上填充 `dp` 表，并在每一步记录路径。
- 最后找到顶部的最大值及其对应的路径。

2. **备忘录法**:
- 使用深度优先搜索（DFS）结合备忘录来避免重复计算。
- `memo` 数组用于存储已经计算过的状态。
- 在每次递归调用中，比较左下和右下的路径和，选择较大的一条路径，并记录路径。

希望这些代码对你有帮助！如果有任何问题或需要进一步解释，请告诉我。