22. 动态规划-自顶向下法

正文

fun dp(n: Int, memo: IntArray): Int {
    // 检查是否已经计算过该值
    if (memo[n] != -1) {
        return memo[n]
    }
    
    // 边界条件
    if (n == 0 || n == 1) {
        memo[n] = n
        return n
    }
    
    // 递归计算并保存结果
    memo[n] = dp(n - 1, memo) + dp(n - 2, memo)
    return memo[n]
}