Python 递归函数奇怪的行为

Question

我使用带有内存功能的递归在 Python 中编写了最长公共(public)子序列:

def print2d(table):
    print '\n'.join([''.join(['{:4}'.format(item) for item in row]) for row in table])

a="123"
b="213"    
m = [[-1]*len(b)]*len(a)
def lcs(i,j):
    print i, j
    print2d(m)

    if i== -1 or j == -1:
        return 0;
    if m[i][j] != -1:
        return m[i][j]

    res = 0
    res = max(res, lcs(i, j-1))
    res = max(res, lcs(i-1, j))
    if a[i] == b[j]:
        res = max(res, 1 + lcs(i-1,j-1))
    m[i][j]=res
    return res

print lcs(len(a)-1,len(b)-1)
print2d(m)

所有这些print语句之所以存在，是因为我没有得到正确的结果，并决定看看该算法是如何工作的。我的发现令我惊讶。如果您自己运行它，您可以看到打印的表格，它们看起来不错，直到:

0 -1
  -1  -1  -1
  -1  -1  -1
  -1  -1  -1
-1 0
  -1  -1  -1
  -1  -1  -1
  -1  -1  -1
0 -1
   0  -1  -1
   0  -1  -1
   0  -1  -1
1 1
   1  -1  -1
   1  -1  -1
   1  -1  -1
1 0
   1  -1  -1
   1  -1  -1
   1  -1  -1
0 1
   1  -1  -1
   1  -1  -1
   1  -1  -1

为什么突然上台阶0 -1整个第一列变成了 0 ？ 因此，我快速创建了 C++ 程序，以相同的方式执行完全相同的操作:

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
using namespace std;
string a = "123",
       b = "213";
int mem[1000][1000];

int lcs(int i, int j) {
    cout << i << " " << j << "\n";
    for(auto i = 0; i < a.length(); i++){
        for(auto j = 0; j < b.length(); j++){
            cout << setw(4) << right << mem[i][j];
        }
        cout << "\n";
    }
    if (i == -1 || j == -1) {
        return 0;
    }
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    int res = 0;
    res = max(res, lcs(i, j - 1));
    res = max(res, lcs(i - 1, j));
    if (a[i] == b[j]) {
        res = max(res, 1 + lcs(i - 1, j - 1));
    }
    mem[i][j] = res;
    return res;
}
int main(){
    memset(mem, -1, sizeof mem );
    int r = lcs(a.length()-1, b.length()-1);
    cout << r << "\n";
    return 0;
}

它按预期工作。对应的表如下所示:

0 -1
  -1  -1  -1
  -1  -1  -1
  -1  -1  -1
-1 0
  -1  -1  -1
  -1  -1  -1
  -1  -1  -1
0 -1
   0  -1  -1
  -1  -1  -1
  -1  -1  -1
1 1
   0  -1  -1
   1  -1  -1
   1  -1  -1
1 0
   0  -1  -1
   1  -1  -1
   1  -1  -1
0 1
   0  -1  -1
   1  -1  -1
   1  -1  -1

我很困惑为什么 Python 和 C++ 代码没有那么不同却会产生如此截然不同的结果。

我是否遗漏了有关 Python 中递归函数如何工作的信息？或者是因为在 Python 中我使用列表列表而不是像 C++ 中那样使用二维数组？

Answer 1

m的初始化是问题所在:

m = [[-1]*len(b)]*len(a)

生成的最终列表使用对 [-1,...,-1] 的同一列表的引用。因此，当您修改 m[0] 处的列表时，您也会修改其他位置。像下面这样的东西应该可以解决这个问题:

m = [[-1 for i in range(len(b))] for j in range(len(a))]