首页 > 其他分享 >120. Triangle刷题笔记

120. Triangle刷题笔记

时间：2023-05-26 22:04:17浏览次数：50

标签：triangle int List len 120 Triangle 刷题 dp row

用DP可以做完

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = [0]*(len(triangle)+1)
        for row in triangle[::-1]:
            for i in range(len(row)):
                dp[i]=row[i]+min(dp[i],dp[i+1])
        return dp[0]

120. Triangle刷题笔记_leetcode

标签：triangle,int,List,len,120,Triangle,刷题,dp,row
From： https://blog.51cto.com/u_16131692/6359370

1480. Running Sum of 1d Array刷题笔记
简单难度的题classSolution:defrunningSum(self,nums:List[int])->List[int]:foriinrange(1,len(nums)):nums[i]+=nums[i-1]returnnums......
1658. Minimum Operations to Reduce X to Zero刷题笔记
用累加和的方法解决，参考该题解classSolution:defminOperations(self,nums:List[int],x:int)->int:cumsum=[0]+list(accumulate(nums))dic={c:ifori,cinenumerate(cumsum)}goal=cumsum[-1]-xans=-float("inf"......
318. Maximum Product of Word Lengths刷题笔记
用的题解classSolution:defmaxProduct(self,words:List[str])->int:d={}forwinwords:mask=0forcinset(w):mask|=(1<<(ord(c)-97))d[mask]=max(d.get(mask,0),......
32. Longest Valid Parentheses刷题笔记
用stack和dp来做classSolution:deflongestValidParentheses(self,s:str)->int:dp,stack=[0]*(len(s)+1),[]foriinrange(len(s)):ifs[i]=='(':stack.append(i)else:......
322. Coin Change刷题笔记
用自底向上的dp算法classSolution:defcoinChange(self,coins:List[int],amount:int)->int:dp=[0]+[float('inf')]*amountforiinrange(1,amount+1):forcoinincoins:ifi-coin>=0:......
1332. Remove Palindromic Subsequences刷题笔记
容易陷入思维盲区，只有a和b的字符串，只会有2个或1个回文classSolution:defremovePalindromeSub(self,s:str)->int:return2-(s==s[::-1])......
52. N-Queens II刷题笔记
回溯算法，参考该题解classSolution:deftotalNQueens(self,n:int)->int:diag1=set()diag2=set()usedCols=set()returnself.helper(n,diag1,diag2,usedCols,0)defhelper(self,n,diag1,diag2,usedCols,......
1192. Critical Connections in a Network刷题笔记
参考这个题解，用的dfsimportcollectionsclassSolution:defcriticalConnections(self,n:int,connections:List[List[int]])->List[List[int]]:defmakeGraph(coonections):graph=collections.defaultdict(list)forconnincon......
1342. Number of Steps to Reduce a Number to Zero刷题笔记
easy题，按照逻辑写就行了classSolution:defnumberOfSteps(self,num:int)->int:step=0whilenum:ifnum%2==0:num=num/2else:num-=1step+=1returnste......
647. Palindromic Substrings刷题笔记
用动态规划可以做，应该可以优化为只有两个表，而且不用每次res都加classSolution:defcountSubstrings(self,s:str)->int:n=len(s)dp=[[0]*nfor_inrange(n)]res=0foriinrange(n-1,-1,-1):forji......

120. Triangle刷题笔记

相关文章

赞助商

阅读排行