c++

C++动态规划怎样解决杨辉三角形

小樊
132
2024-07-05 19:13:30
栏目: 编程语言

在C++中,可以使用动态规划的方法来解决杨辉三角形的问题。动态规划的思想是将原问题拆分成多个子问题,并且保存子问题的解,以减少重复计算。以下是使用动态规划解决杨辉三角形问题的示例代码:

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> result;

    if (numRows <= 0) {
        return result;
    }

    result.push_back({1});

    for (int i = 1; i < numRows; i++) {
        vector<int> row(i + 1, 1);
        for (int j = 1; j < i; j++) {
            row[j] = result[i - 1][j - 1] + result[i - 1][j];
        }
        result.push_back(row);
    }

    return result;
}

int main() {
    int numRows = 5;
    vector<vector<int>> triangle = generate(numRows);

    for (int i = 0; i < triangle.size(); i++) {
        for (int j = 0; j < triangle[i].size(); j++) {
            cout << triangle[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

在上面的代码中,我们定义了一个函数generate来生成杨辉三角形,函数接受一个参数numRows表示要生成的行数。我们使用一个二维向量result来保存每一行的数据,然后使用动态规划的方法依次计算每一行的值并存储在result中。最后,我们打印出生成的杨辉三角形。运行结果如下:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 

这样,我们就使用动态规划的方法成功解决了杨辉三角形问题。

0
看了该问题的人还看了