119. 杨辉三角 II

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
输入: 3
输出: [1,3,3,1]

  • 时间复杂度：O(_rowIndex ^_2)。

  • 空间复杂度：O(1)。不考虑返回值的空间占用。

    1. //二项式性质 动规
    2. func getRow(rowIndex int) []int {
    3.   dp := make([][]int, rowIndex+1)
    5.   for i := range dp {
    6.       dp[i] = make([]int, i+1)
    7.       dp[i][0], dp[i][i] = 1, 1
    8.       for j := 1; j < i; j++ {
    9.           dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    10.       }
    11.   }
    12.   return dp[rowIndex]
    13. }
    //滚动数组 优化空间
func getRow(rowIndex int) []int {
  var pre, dp []int

  for i := 0; i <= rowIndex; i++ {
      dp= make([]int, i+1)
      dp[0], dp[i] = 1, 1
      for j := 1; j < i; j++ {
          dp[j] = pre[j-1] + pre[j]
      }
      pre = dp
  }
  return pre
}

//记忆化递归，从上到下
func getRow(rowIndex int) []int {
    memo := make([][]int, rowIndex+1)
    for i := range memo {
        memo[i] = make([]int, i+1) // 构建memo二维数组
    }

    for j := 0; j < rowIndex+1; j++ { // 计算第rowIndex行的每个元素
        memo[rowIndex][j] = cal(rowIndex, j, memo)
    }
    return memo[rowIndex] // 返回第rowIndex行的子数组
}

func cal(i int, j int, memo [][]int) int {
    if j == 0 || i == j { // 每一行的首尾两项都是1
        return 1
    }

    if memo[i][j] > 0 { // 如果memo[i][j]有值，返回它，避免落入重复的递归
        return memo[i][j]
    }
    // 其他情况，有下面的递归公式      
    memo[i][j] = cal(i-1, j-1, memo) + cal(i-1, j, memo)

    return memo[i][j] 
}