a 为第 i 行的状态，用 for j 来枚举

b 为第i-1行的状态，用 for k 来枚举

c 为第i-2行的状态，用 for u 来枚举

f[i][j][k] 表示在前 i 行中摆放，第 i 行的状态为j，第i-1行的状态为k，的最大值

f[i-1][k][u]表示在前i-1行中摆放，第i-1行的状态为k，第i-2行的状态为u，的最大值

然后加上第i行摆放个数cnt[a]更新最大值，此题的最后一步的为第i-2行

import java.util.*;
class Main{
    private static int n, m;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        //预处理地图
        int[] g = new int[n+3];
        for(int i = 1; i <= n; i++){
            String s = sc.next();
            for(int j = 0; j < m; j++){
                if(s.charAt(j) == 'H'){
                    g[i] += 1 << j;
                }
            }
        }
        //预处理所有的合法状态和状态中1的个数
        List<Integer> states = new ArrayList<>();
        int[] cnt = new int[1<<m];
        for(int i = 0; i < 1 << m; i++){
            if(check(i)){
                states.add(i);
                cnt[i] = count(i);
            }
        }
        //计算状态转移值
        int[][][] f = new int[n+3][states.size()][states.size()];
        for(int i = 1; i <= n+2; i++){
            for(int j = 0; j < states.size(); j++){
                for(int k = 0; k < states.size(); k++){
                    for(int u = 0; u < states.size(); u++){
                        int a = states.get(j);
                        int b = states.get(k);
                        int c = states.get(u);
                        if((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue;
                        if((g[i] & a) != 0 || (g[i-1] & b) != 0) continue;
                        f[i][j][k] = Math.max(f[i][j][k], f[i-1][k][u] + cnt[a]);
                    }
                }
            }
        }
        System.out.println(f[n+2][0][0]);
    }
    private static boolean check(int a){
        for(int i = 0; i < m; i++){
            if((a >> i & 1) == 1 && ((a >> i+1 & 1) == 1 || (a >> i+2 & 1) == 1)){
                return false;
            } 
        }
        return true;
    }
    private static int count(int a){
        int res = 0;
        for(int i = 0; i < m; i++) res += a >> i & 1;
        return res;
    }
}

使用滚动数组对空间进行优化，如需记录前x个状态则数组%x即可，如果只记录前1个状态%1可以省略

本题用到前两种状态对数组%2，如果用到前三种状态就可以%3来处理

import java.util.*;
class Main{
    private static int n, m;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        //预处理地图
        int[] g = new int[n+3];
        for(int i = 1; i <= n; i++){
            String s = sc.next();
            for(int j = 0; j < m; j++){
                if(s.charAt(j) == 'H'){
                    g[i] += 1 << j;
                }
            }
        }
        //预处理所有的合法状态和状态中1的个数
        List<Integer> states = new ArrayList<>();
        int[] cnt = new int[1<<m];
        for(int i = 0; i < 1 << m; i++){
            if(check(i)){
                states.add(i);
                cnt[i] = count(i);
            }
        }
        //计算状态转移值
        int[][][] f = new int[3][states.size()][states.size()];
        for(int i = 1; i <= n+2; i++){
            for(int j = 0; j < states.size(); j++){
                for(int k = 0; k < states.size(); k++){
                    for(int u = 0; u < states.size(); u++){
                        int a = states.get(j);
                        int b = states.get(k);
                        int c = states.get(u);
                        if((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue;
                        if((g[i] & a) != 0 || (g[i-1] & b) != 0) continue;
                        f[i%2][j][k] = Math.max(f[i%2][j][k], f[(i-1)%2][k][u] + cnt[a]);
                    }
                }
            }
        }
        System.out.println(f[(n+2) % 2][0][0]);
    }
    private static boolean check(int a){
        for(int i = 0; i < m; i++){
            if((a >> i & 1) == 1 && ((a >> i+1 & 1) == 1 || (a >> i+2 & 1) == 1)){
                return false;
            } 
        }
        return true;
    }
    private static int count(int a){
        int res = 0;
        for(int i = 0; i < m; i++) res += a >> i & 1;
        return res;
    }
}