2140. Solving Questions With Brainpower

Medium
Description

給定二維陣列 questions，其中 questions[i] = [points_i, brainpower_i]。做第 i 題可以獲得 points_i 分，但接下來 brainpower_i 題必須跳過。也可以選擇不做。求能獲得的最大分數。

Example:

Input: questions = [[3,2],[4,3],[4,4],[2,5]] Output: 5

Intuition#

從後往前 DP：每題選擇「做（跳過後面幾題）」或「不做（繼續下一題）」。

  • 從前往後會需要追蹤跳過的狀態，從後往前更簡潔
  • dp[i] = 從第 i 題開始能獲得的最大分數
  • 做第 i 題：points[i] + dp[i + brainpower[i] + 1]
  • 不做：dp[i + 1]
  • dp[i] = max(做, 不做)

Approaches#

1: Top-Down Memoization#

  • 概念: 從第 0 題開始遞迴，每題選做或不做
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun mostPoints(questions: Array<IntArray>): Long {
        val n = questions.size
        val memo = LongArray(n) { -1L }
        fun dp(i: Int): Long {
            if (i >= n) return 0L
            if (memo[i] != -1L) return memo[i]
            val (points, skip) = questions[i]
            memo[i] = maxOf(
                points + dp(i + skip + 1),  // 做
                dp(i + 1)                    // 不做
            )
            return memo[i]
        }
        return dp(0)
    }
}

⭐2: Bottom-Up DP (Reverse)#

  • 概念: 從最後一題往前計算，每題取做或不做的最大值
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun mostPoints(questions: Array<IntArray>): Long {
        val n = questions.size
        val dp = LongArray(n + 1)
        for (i in n - 1 downTo 0) {
            val (points, skip) = questions[i]
            val next = if (i + skip + 1 < n) dp[i + skip + 1] else 0L
            dp[i] = maxOf(points + next, dp[i + 1])
        }
        return dp[0]
    }
}

🔑 Takeaways#

  • Pattern: 選或不選型 DP — 每個元素做「取/跳」的二元決策，從後往前更自然
  • 關鍵技巧: 反向 DP 避免追蹤「跳過」的狀態；注意用 Long 避免溢位