LeetCode - The World's Leading Online Programming Learning Platform

Intuition

Turn all conditions into a tree and traverse it through DFS to find the answer.

Approach

Step1. Build the tree

We can start from any point in the array, but to maximize the result, it's preferable to begin from 0 or 1.

After selecting an index, the next index must be index+2 or later. (Skip one or more) However, choosing index+4 or later is not meaningful, as index+4 could be the next step of index+2.

Therefore, we choose only index+2 and index+3 as the next step (subtree) each time. Build the tree based on this logic.

Step 2. Handle base cases

Since we are using DFS to travel the tree, we have to handle the base case of recursion.

def dp(...):
    # ...
    if i >= len(nums)-2 and i < len(nums):
        return nums[i]
    if i >= len(nums)-1:
        return 0

Step 3. Handle recursive cases

Find the maximum value from the left subtree and the right subtree, add it to the current value, and return.