LeetCode.119.杨辉三角II（简单）

题目

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

题解

最直观就是求出杨辉三角所有行，取第rowIndex行。
实际每一行由上一行推导而来，不需要存储所有行，只需要保存上一行，递推来就行。

状态转移方程

设dp[r][c]是杨辉三角第r行第c列的数。
左上方的数：dp[r - 1][c - 1]；
右上方的数：dp[r - 1][c]；
dp[r][c] = dp[r - 1][c - 1] + dp[r - 1][c]

空间优化

用一个数组就可以完成每行迭代。
dp[c] = dp[c - 1] + dp[c]

注意事项

更新第c列时，会读取c - 1列的旧值；
但是c - 1列在更新数组的时候已经被新值覆盖了。
解决方案：

从左向右遍历数组时，临时存储一下旧值。
从右向左遍历数组。

代码（kotlin）

class Solution {
    fun getRow(rowIndex: Int): List<Int> {
        val rows = IntArray(rowIndex + 1) { 0 }
        rows[0] = 1
        for (r in 1..rowIndex) {
            for (c in r - 1 downTo 1) {
                rows[c] = rows[c - 1] + rows[c]
            }
            rows[r] = 1
        }
        return rows.toList()
    }
}