解法一：动态规划（普通）
状态定义：f[i]表示nums[1...i]能得到的最大现金；
状态转移方程：为了计算出f[i]，对最后一家即索引i所表示店铺分情况讨论：若小偷不洗劫此店铺，则转化成求子问题f[i - 1]；若小偷洗劫此店铺，按照题目要求不能洗劫相邻的店铺，则转化成求f[i - 2] + nums[i]。对上述两种情况取最大值即为f[i]。

import java.util.*;

public class Main{
    static int N = 100010;
    static int[] nums = new int[N];
    static int[] f = new int[N];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t -- > 0){
            int n = sc.nextInt();
            for(int i = 1; i <= n; i ++) nums[i] = sc.nextInt();

            Arrays.fill(f, 0);
            for(int i = 1; i <= n; i ++){
                f[i] = f[i - 1];
                f[i] = Math.max(f[i], f[Math.max(i - 2, 0)] + nums[i]);
            }
            System.out.println(f[n]);
        }
    }
}

解法二：动态规划（状态机模型）
状态定义：f[i][j]，表示从nums[1...i]这些店铺、且第i家店铺洗劫的状态为j（j只能取0或1，0代表不被洗劫，1代表被洗劫）时，能得到的最大现金。
状态转移方程：分别求解f[i][0]和f[i][1]。对于f[i][0]，已知不洗劫第i家店铺，那么可以从第i-1家店铺的洗劫或不洗劫状态转移过来，f[i][0]为f[i - 1][0]、f[i - 1][1]中的最大值；对于f[i][1]，已知洗劫第i家店铺，那么只能从第i - 1家店铺的不洗劫状态转移过来，就有f[i][1] = f[i - 1][0] + nums[i]。

import java.util.*;

public class Main{
    static int N = 100010;
    static int[] nums = new int[N];
    static int[][] f = new int[N][2];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t -- > 0){
            int n = sc.nextInt();
            for(int i = 1; i <= n; i ++) nums[i] = sc.nextInt();

            // 状态计算
            for(int i = 1; i <= n; i ++){
                f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
                f[i][1] = f[i - 1][0] + nums[i];
            }
            System.out.println(Math.max(f[n][0], f[n][1]));
        }
    }
}