Pythonの再帰関数は、奇妙な行動

Question

私はメモ化で再帰を使用してPythonで最長共通部分列を書かれていますアルゴリズムの仕組み私が見つけたのは私を驚かせた。あなたがそれを自分で実行する場合は、表が印刷され見ることができると彼らはまで[OK]を見て：ステップ0 -1上の突然のすべてが全体の最初の列は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 
    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 

？ だから、私すぐに作成した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++のように2D配列ではないからですか？

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))]