乘法表问题

定义

以a为例

• m[i][j][1] = ∑ ( m[i][k-1][1] m[k][j][3] + m[i][k-1][2] m[k][j][3] + m[i][k-1][3] * m[k][j][1] )
• k∈[i+1,j] , k表示最后求和的位置

  问题解

m[1][n][1]

代码

#include<stdio.h>
const int N = 20;
int table[4][4] = { {0,0,0,0}, 
  {0,2,2,1},
  {0,3,2,1},
  {0,1,3,3} };
//存放表达式
char CharExpression[N];
int IntExpression[N];
int expLen=0;
int m[N][N][4] = {0};//m[i][j][1] 表示exp[i-j] 可以得到值为a,b,c 的加括号方式数
//字母转换为对应数字
int trans(char x) {
  if (x == 'a') {
      return 1;
  }else if (x == 'b') {
      return 2;
  }
  else if (x == 'c') {
      return 3;
  }
}
int main() {
  scanf("%s", CharExpression);//输入
  for (int i = 0; CharExpression[i]!='\0'; i++) {//获得长度
      expLen++;
  }
  for (int i = 1; i <= expLen; i++) {//转换
      IntExpression[i] = trans(CharExpression[i-1]);
  }
  //基础解 表达式长度为1
  for (int i = 1; i <= expLen; i++) {
      m[i][i][1] = 0;
      m[i][i][2] = 0;
      m[i][i][3] = 0;
      m[i][i][IntExpression[i]] = 1;
  }
  //动态规划
  for (int r = 2; r <= expLen; r++) {//表达式长度
      for (int s = 1; s <= expLen - r + 1; s++) {//表达式起点
          int e = s + r - 1;//表达式终点
          for (int k = s + 1; k <= e; k++) {//断点   k=s+1 表示分割[s:e] 为 [s] [s+1,...,e]
              m[s][e][1] += m[s][k - 1][1] * m[k][e][3] + m[s][k - 1][2] * m[k][e][3] + m[s][k - 1][3] * m[k][e][1];
              m[s][e][2] += m[s][k - 1][1] * m[k][e][1] + m[s][k - 1][1] * m[k][e][2] + m[s][k - 1][2] * m[k][e][2];
              m[s][e][3] += m[s][k - 1][2] * m[k][e][1] + m[s][k - 1][3] * m[k][e][2] + m[s][k - 1][3] * m[k][e][3];
          }
      }
  }
  printf("%d", m[1][expLen][1]);
  return 0;
}