Алгоритм динамического программирования с участием комбинаций?

Question

Задача

Так что проблема решается этим алгоритмом

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    int[] memo = new int[nums.length + 1];
    memo[0] = 0;
    memo[1] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int val = nums[i];
        memo[i+1] = Math.max(memo[i], memo[i-1] + val);
    }
    return memo[nums.length];
}

Я не в состоянии следовать этому подходу динамического программирования, я не могу отказаться от идеи итеративного программирования. Я продолжаю хотеть создавать переменные currentMax и т. Д., Но это не имеет смысла.

Можно ли объяснить, что здесь происходит, и закономерность?

Answer 1

В этом паттерне он хранит максимум среди предыдущего результата и текущее значение num в текущей позиции заметки и т. Д.

Answer 2

Просто пытаюсь объяснить природу этой проблемы, и я надеюсь, что она последует - Думайте в терминах, что если есть только два дома < h1 <cost: 90>, h2 <cost: 100>>.Какой будет ответ?Можно было бы пойти на h2.Это наш базовый случай проблемы, и мы будем расширять его отсюда. Расширение - 3 дома - <h1 <cost: 90>, h2 <cost: 100>, h3 < cost: 75>>.Если вы добываете h2, вы не можете добывать <h1> and <h3>, но вы хотите добыть <h1> and <h3>, потому что это дает вам больше суммы.поэтому, рекурсивно, в текущий момент времени t, если я сохраню свой результат в переменной dp и recursive func(int index,int[] array), я могу ответить в виде dp[index]=max(arr[index]+dp[index+2],dp[index+1]).В нем говорится, что если я получу лут ith House, то я не смогу лут next house, так что остающаяся проблема, которую нужно решить, это i+2th index