LeetCode Entry

2140. Solving Questions With Brainpower

01.04.2025 medium 2025 kotlin rust

Max sum of (points, skip next) pairs

2140. Solving Questions With Brainpower medium blog post substack youtube

1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/945

Problem TLDR

Max sum of (points, skip_next) pairs #medium #dp

Intuition

At each position make a decision: take or skip. We should know before-hand the oprimal result of (current + skip) position. Go from the tail, or do a DFS + cache.

Approach

  • use size + 1 for dp array to simplify the logic

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun mostPoints(q: Array<IntArray>): Long {
        val dp = LongArray(q.size + 1)
        for (i in q.size - 1 downTo 0) dp[i] = max(
            dp[min(q.size, i + q[i][1] + 1)] + q[i][0], dp[i + 1])
        return dp[0]
    }



    val dp = HashMap<Int, Long>()
    fun mostPoints(q: Array<IntArray>, i: Int = 0): Long = if (i >= q.size) 0 else
    dp.getOrPut(i) { max(mostPoints(q, i + q[i][1] + 1) + q[i][0], mostPoints(q, i + 1)) }



    pub fn most_points(q: Vec<Vec<i32>>) -> i64 {
        let mut dp = vec![0; q.len() + 1];
        for i in (0..q.len()).rev() { dp[i] = dp[i + 1].max(
            dp[q.len().min(i + 1 + q[i][1] as usize)] + q[i][0] as i64 )}
        dp[0]
    }



    long long mostPoints(vector<vector<int>>& q) {
        int n = size(q); vector<long long> dp(n + 1, 0);
        for (int i = n - 1; i >= 0; --i) dp[i] = max(dp[i + 1],
            dp[min(n, i + 1 + q[i][1])] + q[i][0]);
        return dp[0];
    }