Boolean Parenthesization问题动态规划代码报错：输入T^F|F输出异常

问题描述 #

实现Boolean Parenthesization问题的动态规划代码运行异常，输入N=5、表达式T^F|F时输出0，正确结果应为2。

测试用例详情 #

输入 #

5
T^F|F

我的输出 #

0

预期输出 #

2

错误代码 #

class Solution {
    static int countWays(int N, String S) {
        int dp[][][] = new int[N][N][2];
        int mod = (int) 1e9;
        for (int i = 0; i < N; i++) {
            if (S.charAt(i) == 'T') {
                dp[i][i][1] = 1;
                dp[i][i][0] = 0;
            } else if (S.charAt(i) == 'F') {
                dp[i][i][1] = 0;
                dp[i][i][0] = 1;
            }
        }
        
        for (int i = N-1; i >= 0; i--) {
            for (int j = 0; j < N; j++) {
                for (int isTrue = 0; isTrue < 2; isTrue++) {
                    int ways = 0;

                    if (i > j)
                        continue;   
                    
                    for (int k = i+1; k < j; k += 2) {
                        int lt = dp[i][k-1][1];
                        int lf = dp[i][k-1][0];
                        int rt = dp[k+1][j][1];
                        int rf = dp[k+1][j][0];
                        
                        if (S.charAt(i) == '&') {
                            if (isTrue == 1) {
                                ways = (ways + lt*rt) % mod;
                            } else
                                ways = (ways + lt*rf + lf*rf + lf*rt) % mod;
                        } else if (S.charAt(i) == '|') {
                            if (isTrue == 1)
                                ways = (ways + lt*rt + lt*rf + lf*rt) % mod;
                            else
                                ways = (ways + lf*rf) % mod;
                        } else {
                            if (isTrue == 1)
                                ways = (ways + lt*rf + lf*rt) % mod;
                            else
                                ways = (ways + lt*rt + lf*rf) % mod;
                        }
                    }

                    dp[i][j][isTrue] = ways;
                }
            }
        }

        return dp[0][N-1][1];
    }
}

错误分析与修复 #

核心错误点 #

1. 操作符获取错误：代码中用S.charAt(i)判断操作符，但i是子串起始的操作数位置，当前分割点的操作符应该在k位置（k是操作符索引，步长为2），这是导致结果为0的直接原因。
2. 循环范围逻辑错误：
   • 内层j循环不应从0开始，而应从i+2开始（因为有效子串长度必须为奇数，i到j至少间隔2才能包含一个操作符和两个操作数）。
   • 原循环顺序会大量处理i > j的无效情况，效率低下且易出错。

修复后的代码 #

class Solution {
    static int countWays(int N, String S) {
        int dp[][][] = new int[N][N][2];
        int mod = (int) 1e9;
        
        // 初始化单个字符的情况（仅操作数位置）
        for (int i = 0; i < N; i += 2) {
            dp[i][i][1] = S.charAt(i) == 'T' ? 1 : 0;
            dp[i][i][0] = S.charAt(i) == 'F' ? 1 : 0;
        }
        
        // 遍历子串长度，从3开始（步长2，符合表达式结构）
        for (int len = 3; len <= N; len += 2) {
            // 遍历所有可能的起始索引
            for (int i = 0; i <= N - len; i += 2) {
                int j = i + len - 1; // 子串结束索引
                dp[i][j][0] = dp[i][j][1] = 0;
                
                // 遍历所有操作符位置
                for (int k = i + 1; k < j; k += 2) {
                    char op = S.charAt(k);
                    int lt = dp[i][k-1][1];
                    int lf = dp[i][k-1][0];
                    int rt = dp[k+1][j][1];
                    int rf = dp[k+1][j][0];
                    
                    // 根据操作符计算真/假的组合数
                    if (op == '&') {
                        dp[i][j][1] = (dp[i][j][1] + lt * rt) % mod;
                        dp[i][j][0] = (dp[i][j][0] + lt * rf + lf * rt + lf * rf) % mod;
                    } else if (op == '|') {
                        dp[i][j][1] = (dp[i][j][1] + lt * rt + lt * rf + lf * rt) % mod;
                        dp[i][j][0] = (dp[i][j][0] + lf * rf) % mod;
                    } else if (op == '^') {
                        dp[i][j][1] = (dp[i][j][1] + lt * rf + lf * rt) % mod;
                        dp[i][j][0] = (dp[i][j][0] + lt * rt + lf * rf) % mod;
                    }
                }
            }
        }
        
        return dp[0][N-1][1];
    }
}

修复说明 #

1. 初始化优化：只遍历操作数索引（步长2），操作符位置无需初始化。
2. 循环顺序调整：按子串长度从小到大遍历，确保计算长串时短串的结果已就绪。
3. 操作符修正：通过S.charAt(k)获取当前分割点的操作符，符合问题逻辑。
4. 范围修正：j由i + len -1计算得出，避免无效的子串范围。

内容的提问来源于stack exchange，提问作者yash saini