问题描述：给定一组数字，要求从这组数字里找出非 相邻数字和的最大值。 举例： 输入：4 1 1 9 1 输出：13（9+4） 输入：1 2 4 1 7 8 3 输出：13 （8+4+1） 代码实现：
public class Demo { //递归实现 public static int rec_opt(int[] arr, int i) { if (i == 0) return arr[0]; else if (i == 1) return arr[0] > arr[1] ? arr[0] : arr[1]; else { int a = rec_opt(arr, i - 2) + arr[i]; int b = rec_opt(arr, i - 1); return a > b ? a : b; } } //动态规划实现 public static int dp_opt(int[] arr) { int[] opt = new int[arr.length]; opt[0] = arr[0]; opt[1] = arr[0] > arr[1] ? arr[0] : arr[1]; for (int i = 2; i < opt.length; i++) { int a = opt[i - 2] + arr[i]; int b = opt[i - 1]; opt[i] = a > b ? a : b; } return opt[arr.length - 1]; } //测试 public static void main(String[] args) { int[] arr = { 4, 1, 1, 9, 1 }; System.out.println(dp_opt(arr)); System.out.println(rec_opt(arr, arr.length - 1)); } }