python - leetcode 1039 之 Python 解决方案 vs C++ 解决方案
问题描述
我用python写了一段代码。
class Solution(object):
def minScoreTriangulation(self, A):
self.dp = [[-1]*len(A)]*len(A)
ret = self.calc(A, 0, len(A)-1)
return ret
def calc(self, A, x, y):
if math.ceil(y-x) < 2:
return 0
if self.dp[x][y] != -1:
return self.dp[x][y]
mn = sys.maxint
for i in range(x+1, y):
mn = min(mn, (self.calc(A, x, i) + self.calc(A, i, y) + A[x]*A[y]*A[i]))
self.dp[x][y] = mn
return mn
我还用相同的逻辑编写了一个 C++ 解决方案。
class Solution {
public:
int minScoreTriangulation(vector<int>& A) {
vector<int> row(A.size(), -1);
vector<vector<int>> dp(A.size(), row);
int ret =calc(dp, A, 0, A.size()-1);
return ret;
}
int calc(vector<vector<int>>& dp, vector<int>& A, int x, int y)
{
if ((y-x) < 2)
return 0;
if(dp[x][y] != -1) return dp[x][y];
int mn = INT_MAX;
for( int i=x+1; i<y ; i++)
{
mn = min(mn, calc(dp, A, x, i)+calc(dp, A, i, y)+A[x]*A[y]*A[i]);
}
dp[x][y] =mn;
return mn;
}
};
python 解决方案给了我错误的答案。有人可以解释一下我的 python 解决方案有什么问题吗?
解决方案
问题是这一行:
self.dp = [[-1]*len(A)]*len(A)
在python中,你不能用这种方式来初始化一个二维数组,因为它会引用同一个[-1]*len(A)
,改成:
self.dp = [[-1]*len(A) for i in range(len(A))]
它会正常工作。
推荐阅读
- azure - 为托管服务身份添加访问策略
- scala - 在单个 JVM 中运行多个 SparkContext,或在 intellij env 中创建多个 JVM
- php - 如何防止每次页面重新加载时将用户数据插入数据库?
- java - GSON 输出空数组值
- rest - 如何在 CSV 数据集配置中按名称读取实际文件内容 - Jmeter
- jquery - 如何检查第三方 jquery 文件是否完全加载
- ember.js - Ember.js:并行加载父子模型
- flutter - TextEditingController 不会在 Web 上更改 TextEdit 的文本。可能是 EditText 的其他解决方案吗?
- ubuntu - 在具有非 gui 模式的 ubuntu jmeter 上运行脚本时出错
- html - Chrome/Safari中空的意外定位