pascals|pascals triangle ii（杨辉三角、帕斯卡三角）
题目描述
Given an index k, return the k th row of the Pascal's triangle.
For example, given k = 3,
Return[1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
题目大意
给定一个索引值k，返回杨辉三角中第k行索引的结果
例如，给定：k=3，
返回：[1,3,3,1]
空间复杂度要求为O(k)。
思路
也是一个杨辉三角的问题，但是这个题不要求返回整个杨辉三角，只要求返回索引行的结果，而且要求空间复杂度为O(k)。
因此想到用动规的思想，用一维数组的动态更新来模拟二维数组，但是，考虑每一行的时候，当从前向后递归时是有后效影响的，因此采用从后向前迭代的方式。
代码
#include
#include
using namespace std;
vector getRow(int rowIndex)
{
rowIndex++;
// 行索引加一是真正的行数
vector res(rowIndex, 1);
// 第一二行均为1，从第三行才需要进行计算操作
// 因此索引从2开始
for(int i=2;
i0;
j--)
{
// 每次从后向前迭代
res[j] = res[j-1] + res[j];
}
}return res;
}int main()
{
vector res;
int n;
while(true)
{
cout<<"输入：";
cin>>n;
res = getRow(n);
cout<<"输出：";
for(int i=0;
i 运行结果
文章图片
【pascals|pascals triangle ii（杨辉三角、帕斯卡三角）】以上。
推荐阅读
- 牛客挑战赛39(A（枚举+递增+二分）,B（二分+hash）,C（线段树-等差数组）,E(杨辉三角组合数))
- 120. Triangle
- Codeforces Round #643 (Div. 2) C. Count Triangles 题解（思维）
- 刷题|D - Count Triangles CodeForces - 1355C
- python|python 打印杨辉三角
- 【C语言】打印出杨辉三角形（要求打印出10行）
- codeforce|Codeforces Round #643 (Div. 2) C. Count Triangles-- 差分、前缀和
- 【每日一题】【算法题】【杨辉三角】给定一个非负索引|【每日一题】【算法题】【杨辉三角】给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行
- C语言（利用一维数组输出杨辉三角）
- C++实现LeetCode(118.杨辉三角)