【動态規劃】求數組不相鄰元素之和最大

這題想了半天也沒搞出來，想到了遞歸的方法，但是依然沒有完整的思路最後參考了一下大佬的解法，才了解了其要義。

public static void main(String[] args) {
        int[] since = {1, 2, 4, 1, 7, 8, 23,9,4,22};
        System.out.println(getMax(since, since.length-1));
    }


    public static int getMax(int[] arr, int i) {
        if (i == 0) {
            return arr[0];
        } else if (i == 1) {
            int max = Math.max(arr[0], arr[1]);
            return max;
        } else {
            int a = getMax(arr, i - 2) + arr[i];
            int b = getMax(arr, i - 1);
            int max = Math.max(a, b);
            return max;
        }
    }
           

第一種遞歸的方法，其解法的精髓便是這兩行了：

int a = getMax(arr, i - 2) + arr[i];
int b = getMax(arr, i - 1);
           

arr[i]可以了解為數組的最後一個元素，這裡可以分為兩種情況，第一種：子數組（求得和最大的所有元素組成的數組）包括arr[i]，第二種：子數組不包括a[i]。

a[0] , a[1] , a[2] , a[3] …… a[i-2] , a[i-1] , a[i]

第一種，假如子數組包括a[i]：

因為不相鄰，說明子數組是由前n-2項求得不相鄰元素之和最大，加上最後一項。

int a = getMax(arr, i - 2) + arr[i];
           

第二種，假如子數組不包括a[i]：那就說明原數組有沒有a[i]都行，那索性就去掉吧，接着求前i-1項。

int b = getMax(arr, i - 1);