leetcode 1039 Python 解法 vs C++ 解法-6ren

leetcode 1039 Python 解法 vs C++ 解法

转载作者：行者123 更新时间：2023-11-28 01:21:34

28

4

<分区>

Leetcode 1039

我用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 解决方案有什么问题。

28

4

0

文章推荐： javascript - 在mvc4中使用ajax.actionlink导致刷新页面

文章推荐： javascript - 只有一个应用程序在 DOM 中工作

文章推荐： javascript - Drupal Bootstrap 滚动与 Readmore 插件冲突

Leetcode: Binary Tree Paths(LeetCode：二叉树路径)
我正在解决以下leetcode问题：。。递归解是平凡的，所以我试着想出迭代解。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与标准DFS不同，因为
Leetcode: Binary Tree Paths(LeetCode：二叉树路径)
我正在解决以下leetcode问题：。。递归的解决方案是微不足道的，所以我试图拿出迭代的解决方案。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与
javascript - Javascript 中的两个 Sum Leetcode - 代码看起来正确，但 Leetcode 说它是错误的
我正在处理 'Two Sum' problem in Leetcode . 我确信这段代码是正确的，我已经在 Repl 中对其进行了测试，它看起来是正确的，但 Leetcode 给了我一个错误。这是
python - LeetCode 762 为什么单独的代码在 Jupyter Notebook 中有效，而在 Leetcode 中无效
我正在研究 leetcode“762. 二进制表示中设置位的质数”，并且我测试了我的代码在 Jupiter Notebook 上运行良好，当我迁移到 leetcode 时，它显示 null 作为最
LeetCode：搜索二维矩阵题解
题干请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：每一行的数字都从左到右排序每一行的第一个数字都比上一行最后一个数字大用例例如对于下面矩阵： [ [1,
LeetCode 单调栈内容小结
LeetCode Monotone Stack Summary 单调栈小结所谓的单调栈 Monotone Stack，就是栈内元素都是单调递增或者单调递减的，有时候需要严格的单调递增或递减，根据
LeetCode 二叉树相关Easy题 --- 二叉树
第一题: 合并二叉树 LeetCode 617 : 合并二叉树描述: 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的
和为k的子数组 LeetCode 560
和为k的子数组 LeetCode 560 和为k的不重复子数组个数(包含不连续)：和为k的子数组 LeetCode 560 Example 1: Input:nums=[1,1,1],k=2 Ou
[Leetcode]13. 罗马数字转整数
1.题目描述：难度：简单描述：罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符数值 I 1 V 5 X
[Leetcode]9. 回文数
1.题目描述：难度：简单描述：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，1
[Leetcode]26. 删除有序数组中的重复项
一、题目描述难道：简单描述：给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。由于在
[Leetcode]14. 最长公共前缀
一、题目描述难度：简单描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。示例 1：输入：strs = ["flower","flow","flig
[Leetcode]21. 合并两个有序链表
一、题目描述难度：简单描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1：输入：l1 = [1,2,4], l2 = [1,3,4
【LeetCode】 - 20.有效的括号
@TOC 题目描述给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序
javascript - 合并两个列表 LeetCode
我已经在 Repl.it 网站上解决了这个问题，但是当我在 LeetCode 上提交代码时，它给出了一个 typeError，我将把它粘贴在这里: Line 29 in solution.js
javascript - leetcode 合并排序数组
var merge = function(nums1, m, nums2, n) { //contcating two array let array = nums2.concat(
javascript - leetcode 两数相加算法
我正在做以下leetCode问题:https://leetcode.com/problems/add-two-numbers/ 我不确定为什么我的一个测试用例失败了所以问题是 You are giv
python - Leetcode 在无可争议的正确答案时声称错误答案
我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):
java - LeetCode 中的递归和回溯是如何工作的？
该函数将反向打印链表的节点: void recur(ListNode head) { if(head == null) return; recur(head.next); tm
python - Leetcode 在无可争议的正确答案时声称错误答案
我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):

首页

博学

6Ren·AI

商城

leetcode 1039 Python 解法 vs C++ 解法