以下问题来自 Vazirani 等人的动态规划一章。人。
[6.6]让我们在三个符号a上定义一个乘法运算（×）；乙; c 根据下表：
因此，a × a = b 、 a × b = b 等。
找到一个有效的算法来检查这些符号的字符串，比如说
bbbbac，并决定是否可以将字符串括起来，使得结果表达式的值是a。例如，在输入时，bbbbac您的算法应该返回yes，因为((b(bb))(ba))c = a.
将其映射到此处给出的计算布尔括号数的问题。在那个问题中，你会得到一个布尔表达式，形式为
T或F和T xor T
并且您需要找到用括号括起来的方法的数量，以便它评估为真。
我们可以将or、and、xor视为遵循某些规则（T xor F = T 等）并作用于取值 T 或 F 的操作数的运算符。
对于我们最初的问题，我们可以将 a,b,c 视为具有乘法 (x) 的操作数，如给定表所定义的那样提供规则。
上述方法有意义还是有更简单的方法？
是的，您的方法应该类似于您提到的问题。一般来说，如果有n 个符号（而不是你在这个问题中提到的 3 个或你给出链接的问题中的 2 个），你应该做这样的事情 -
#include <stdio.h>
#include <string.h>
#define MAXL 500
#define MAXN 100
int isPossible[MAXL][MAXL][MAXN];
int matrix[MAXN][MAXN]; //multiplication table
char str[MAXN+1];
int L;
int go(int start, int end, int need) {
if(start > end) return 0;
if(isPossible[start][end][need] != -1) return isPossible[start][end][need];
int i,x,y;
for(i = start; i < end; i++) {
for(x = 0; x < MAXN; x++) {//you can optimize these x & y loops by pre-determining which combinations can give you 'need'
for(y = 0; y < MAXN; y++) if(matrix[x][y] == need) {
if(go(start, i, x)==1 && go(i+1, end, y)==1 ) {
isPossible[start][end][need] = 1;
return 1;
}
}
}
}
return 0;
}
int main() {
while(scanf(" %s",str)==1) {
L = strlen(str);
memset(isPossible, -1, sizeof(isPossible));
go(0, L-1, 'a');
}
return 0;
}
请注意，这不是经过测试的完整源代码。
特别是对于问题中给出的产品规则，我试图在输入中找到给出解决方案的模式，但很快发现在没有解决方案的输入中找到模式更容易。例如：b*或者c*甚至c*b*不允许一个解决方案。查看 3 长、4 长、5 长的输入，我可以为没有解决方案的输入推导出这个正则表达式模式：
^(c*([ab]?a?a?b+)?|(aa|b|c*a)c*a|bac*(ab)?b*)$
所以这里基本上有三种替代模式：
c*([ab]?a?a?b+)?
(aa|b|c*a)c*a
bac*(ab)?b*
我对最多 10 个字符的所有可能输入进行了测试，没有出现新的模式。
此正则表达式将在线性时间内测试任何输入。
对于一般情况（以及测试上述正则表达式解决方案），您可以结合记忆化（动态编程）使用一种分而治之的方法。
您实际上可以存储带有括号的字符串，以获取给定范围的解决方案。
至于子范围，您不知道所需的结果是什么，您可以继续，直到找到任何可能结果的解决方案（然后停止），或者继续直到检查完所有分区。因此，调用者将为每个可能的结果获得一个解决方案（非空、带括号的字符串）或无（空字符串）。
这是在交互式 JavaScript 片段中实现的想法（可以轻松地采用不同的乘法矩阵）。输入输入，如果有解决方案将立即出现。输入大小限制为 28 个字符，因为对于较长的输入，该过程需要太多时间才能愉快地工作。
该片段还包括基于正则表达式的检查：
const a = 0, b = 1, c = 2;
const mul = [
[b, b, a],
[c, b, a],
[a, c, c]
];
function solve(str, outcome) {
// Convert input letters to numbers (a -> 0, b -> 1, ...etc)
const expr = Array.from(str.toLowerCase(), ch => ch.charCodeAt() - "a".charCodeAt());
const memo = new Map;
function recur(start, end) {
let key = start * str.length + end; // unique identifier for the range (start, end)
let solution = memo.get(key); // retrieve from memoization
if (!solution) { // Not memoized yet
solution = Array(mul.length).fill(""); // Start by indicating it is not possible to get any outcome
if (start + 1 === end) { // base case with one value
solution[expr[start]] = str[start];
} else if (start + 2 === end) { // base case with two values
solution[mul[expr[start]][expr[start+1]]] = "(" + str.slice(start, end) + ")";
} else { // Case for which recursion will be used
let unsolvedCount = mul.length;
// Split expression at any possible point
for (let split = start + 1; split < end; split++) {
const left = recur(start, split);
const right = recur(split, end);
for (const leftRes in mul) {
if (left[leftRes]) { // For every possible solution at the left
for (const rightRes in mul) {
if (right[rightRes]) { // ... and every possible solution at the right
const product = mul[leftRes][rightRes]; // ... perform the product
if (!solution[product]) { // We didn't have this outcome yet
solution[product] = "(" + left[leftRes] + right[rightRes] + ")";
// Allow for quick exit when for all possible outcomes we have a solution
unsolvedCount--;
if (unsolvedCount === 0) return solution;
}
}
}
}
}
}
}
memo.set(key, solution); // Remember the work done for this range
}
return solution;
}
// Get the solution for the wanted outcome and remove the outermost parentheses, if any.
// An empty string means there is no solution with that outcome
return recur(0, expr.length)[outcome].replace(/^\(|\)$/g, "");
}
const regex = /^(c*([ab]?a?a?b+)?|(aa|b|c*a)c*a|bac*(ab)?b*)$/;
// I/O handling:
let input = document.querySelector("input");
let outputs = document.querySelectorAll("span");
input.addEventListener("input", refresh);
function refresh() {
let str = input.value;
if (!/^[abc]*$/.test(str)) {
outputs[0].textContent = "Invalid input";
outputs[1].textContent = "";
return;
}
let solution = solve(str, a);
outputs[0].textContent = solution || "No solution";
let decision = !regex.test(str);
outputs[1].textContent = decision ? "There is a solution" : "No solution";
}Input: <input size="28" maxlength="28"><br>
Solution: <span></span><br>
Regex: <span></span>我们可以通过动态规划伪算法来解决这个问题， 可以在这里找到。
/**
* Parenthesizing a string so that expression takes a given value
*/
import java.util.*;
class Solution
{
static boolean func(int[][] matrix, int[] str, int n, int symbol)
{
Set<Integer>[][] T = new Set[n][n];
// Assign the value
for(int i=0; i<n; i++)
{
T[i][i] = new HashSet<Integer>();
T[i][i].add(str[i]);
}
for(int gap = 1; gap<n; gap++)
{
for( int i = 0, j = gap; j<n; i++, j++)
{
T[i][j] = new HashSet<Integer>();
for(int k=i; k < i+gap; k++)
{
Iterator<Integer> outer = T[i][k].iterator();
while(outer.hasNext())
{
int elementOuter = outer.next();
Iterator<Integer> inner = T[k+1][j].iterator();
while(inner.hasNext())
{
int elementInner = inner.next();
int val = matrix[elementOuter][elementInner];
T[i][j].add(val);
}
}
}
}
}
if(T[0][n-1].contains(symbol))
return true;
return false;
}
public static void main(String args[] ) throws Exception
{
int[] stringNew = {1, 1, 1, 1, 0}; // for String "bbbbac"
int element = 3;
/**
* Here a -> 0
* b -> 1
* c -> 2
*
* Table Equivalent Table
* * a b c \ * 0 1 2
* a b b a ------\ 0 1 1 0
* b c b a ------/ 1 2 1 0
* c a c c / 2 0 2 2
*/
int matrix[][] = {{1, 1, 0},{2, 1, 0},{0, 2, 2}}; //multiplication table
System.out.println(func(matrix, stringNew, stringNew.length, 0));
}
}