在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
這樣,我們就使用動態規劃的方法成功解決了楊輝三角形問題。