第三题100 public long GetNumOfExpress(String express, boolean desired) { // write code here if (express==null || express.length()==0 || !isValid(express.toCharArray())){ return 0; } char[] str = express.toCharArray(); int len = str.length; long[][] dpTrue = new long[len][len]; long[][] dpFalse = new long[len][len]; if (str[0]=='0'){ dpTrue[0][0] = 0; dpFalse[0][0] = 1; } else { dpTrue[0][0] = 1; dpFalse[0][0] = 0; } // 区间dp for (int j=0;j<len;j+=2){ if (str[j]=='0'){ dpTrue[j][j] = 0; dpFalse[j][j] = 1; } else { dpTrue[j][j] = 1; dpFalse[j][j] = 0; } for (int i=j-2;i>=0;i-=2){ for (int k=i+1;k<j;k+=2){ if (str[k]=='&'){ dpTrue[i][j] += dpTrue[i][k-1]*dpTrue[k+1][j]; dpFalse[i][j]+= dpTrue[i][k-1]*dpFalse[k+1][j]+dpFalse[i][k-1]*dpTrue[k+1][j]+dpFalse[i][k-1]*dpFalse[k+1][j]; } else if (str[k]=='|'){ dpTrue[i][j] += dpTrue[i][k-1]*dpTrue[k+1][j] + dpTrue[i][k-1]*dpFalse[k+1][j] + dpFalse[i][k-1]*dpTrue[k+1][j]; dpFalse[i][j] += dpFalse[i][k-1]*dpFalse[k+1][j]; } else { dpTrue[i][j] += dpTrue[i][k-1]*dpFalse[k+1][j] + dpFalse[i][k-1]*dpTrue[k+1][j]; dpFalse[i][j] += dpTrue[i][k-1]*dpTrue[k+1][j] + dpFalse[i][k-1]*dpFalse[k+1][j]; } } } } if (desired) return dpTrue[0][len-1]; else return dpFalse[0][len-1]; } private boolean isValid(char[] str){ boolean flag = true; for (char c:str){ if (flag){ if (c!='0' && c!='1') return false; flag = false; } else { if (c!='|' && c!='&' && c!='^') return false; flag = true; } } if (flag) return false; return true; }