题目描述
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
题解
思路1:动态规划
dp[i][0] = 1
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (0<j<i)
dp[i][i] = 1
static public func getRow1(_ rowIndex: Int) -> [Int] {
if rowIndex < 0 {return [Int]()}
if rowIndex == 0 {return [1]}
var dp = Array(repeating: Array(repeating: 0, count: rowIndex+1), count: rowIndex+1)
dp[0][0] = 1
for i in 1...rowIndex {
dp[i][0] = 1
dp[i][i] = 1
for j in 1..<I {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
}
}
return dp[rowIndex]
}
优化
f[i][j] 只与f[i-1][...]有关，与f[i−2][..] 及之前的状态无关
我们使用两个长度为n的一维数组进行转移，将i根据奇偶性映射到其中一个一维数组，那么i−1 就映射到了另一个一维数组。这样我们使用这两个一维数组，交替地进行状态转移
static public func getRow2(_ rowIndex: Int) -> [Int] {
if rowIndex < 0 {return [Int]()}
if rowIndex == 0 {return [1]}
var dp = Array(repeating: Array(repeating: 0, count: rowIndex+1), count: 2)
dp[0][0] = 1
for i in 1...rowIndex {
let curr = I%2
let prew = 1-curr
dp[curr][0] = 1
dp[curr][i] = 1
for j in 1..<I {
dp[curr][j] = dp[prew][j] + dp[prew][j-1]
}
}
return dp[rowIndex%2]
}
优化
从i到0递减地枚举j，只使用一个长度为n的一维数组f，完成状态转移
为什么只有在递减地枚举j时，才能省去一个一维数组？当我们在计算位置(i,j) 时，f[j+1] 到f[i] 已经是第i 行的值，
而f[0] 到f[j] 仍然是第i−1 行的值。此时我们直接通过f[j]=f[j−1]+f[j]进行转移，恰好就是在(i−1,j−1) 和(i−1,j) 中进行选择。
但如果我们递增地枚举j，那么在计算位置(i,j) 时，f[0] 到f[j−1] 已经是第i行的值。如果我们仍然使用上述状态转移方程，那么是在(i,j−1) 和(i−1,j) 中进行选择，就产生了错误
static public func getRow3(_ rowIndex: Int) -> [Int] {
if rowIndex < 0 {return [Int]()}
if rowIndex == 0 {return [1]}
var dp = Array(repeating: 0, count: rowIndex+1)
dp[0] = 1
for i in 1...rowIndex {
dp[i] = 1
for j in (1..<i).reversed() {
dp[j] = dp[j] + dp[j-1]
}
dp[0] = 1
}
return dp
}
思路2:线性递推
C(n,m) = A(n,m)/A(m,m) = A(n,n)/(A(n-m,n-m)*A(m,m)) = n! / ((n-m)! * m!)
C(n,m) = n! / ((n-m)! * m!) = n! / ((n-m+1)! * (m-1)!) * ((n-m+1)/m) = C(n,m-1) * (n-m+1)/m
static public func getRow4(_ rowIndex: Int) -> [Int] {
if rowIndex < 0 {return [Int]()}
if rowIndex == 0 {return [1]}
var dp = Array(repeating: 0, count: rowIndex+1)
dp[0] = 1
for i in 1...rowIndex {
dp[i] = dp[i-1] * (rowIndex-i+1)/I
}
return dp
}
类似:三角形最小路径和
参考：https://leetcode-cn.com/problems/pascals-triangle-ii
https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang-hui-san-jiao-ii-by-leetcode-solutio-shuk/
