【问题描述】 设S1[1..n]和S2[1..m]是两个序列, 把它们并排放到一起进行比较,在比较时可以在某个序列的字符之间插入空格, 插入空格的目的是使它们局部的相同区域能够对应. (1)如果两个对应字符相等,那么赋权值 2; (2)如果对应字符不等,赋权值-2; (3)如果一个是字符,一个是空格,赋权值-1. 求权值最大的对准方式。

这是一个典型的字符串匹配问题，可以使用动态规划来解决。

令dp[i][j]表示S1前i个字符和S2前j个字符的最大权值对准方式，则有以下递推式：

$$dp[i][j]=\max\begin{cases}dp[i-1][j-1]+2, &\text{if }S1[i]=S2[j]\\ dp[i-1][j-1]-2, &\text{if }S1[i]\neq S2[j]\\ dp[i-1][j]-1, &\text{if }S1[i]\neq \text{' '}\text{ and }S2[j]=\text{' '}\\ dp[i][j-1]-1, &\text{if }S1[i]=\text{' '}\text{ and }S2[j]\neq \text{' '}\\ dp[i-1][j-1]-1, &\text{otherwise} \end{cases}$$

其中，第一种情况表示当前字符匹配，赋值为2；第二种情况表示当前字符不匹配，赋值为-2；第三、四种情况表示当前字符与空格匹配，赋值为-1；最后一种情况表示不匹配，赋值为-1。

最终的答案则为$dp[n][m]$，即S1和S2的最大权值对准方式。

代码如下：