动态规划-大盗阿福 java.cui

解题思路:  理解题目意思后，写出推导式dp[j]=max(arr[j]+dp[j-2],dp[j-1])即可得出答案，这个过程需要多刷题才能有更深一步的体会。

动态规划我现在做了几题，还处于入门阶段，但是目前接触下来，我发现最重要的是能够写出推导式，思路一定要特别明确，还有构造出自己到底需要什么样的dp数组，我们不是要去关注dp的下标，而是想要解的数组的下标。dp数组就是一个备忘录。动态规划就是空间换时间的非常好的方法。

实际上这题肯定有比我更好的思路和解法，但是我认为我写的这个比较符合我自己的逻辑
注意事项:

参考代码:

import java.util.Arrays;
import java.util.Scanner;

public class Main {

//完成初始化
   static int T, N;
   static Scanner sc = new Scanner(System.in);
   static int[] arr;
   static int[] dp;

   public static void price() {
       N = sc.nextInt();
       arr = new int[N];
       for (int i = 0; i < N; i++) {
           arr[i] = sc.nextInt();
       }
       System.out.println(sum());
   }

   public static int sum() {
       dp = new int[N];
       dp[0] = arr[0];     //第一家的钱赋给dp[0][0]
       if (N > 1) {          //当商店大于1时
           dp[1] = Math.max(arr[0], arr[1]);   //第一家的钱和第二家比较
           for (int i = 2; i < N; i++) {            

//2进来的时候，当大于等于三家的时候，进行比较      

//拿最简单的3个就是偷1和3  还有偷2  就是i=2开始比较

//第二家和（第一家加上第三家）比较     i++  i=3时   第三家和第二家加上第四家比较，一直在循环取最大值

//这里开始比较：前一家不偷，那就是偷了前一家的前一家加上这一家。

               dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);     
           }
       }
       return dp[N - 1];
   }

   public static void main(String[] args) {
       T = sc.nextInt();
       for (int i = 0; i < T; i++) {
           price();
           Arrays.fill(dp, 0);  //对dp数组初始化，这一步是必要的否则后续会出错
       }
   }
}