119 杨辉三角2

一行一行往下推

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        if rowIndex == 1:
            return [1,1]
        rel = [1,1]
        for i in range(rowIndex-1):
            currel = [1]
            for index,_ in enumerate(rel[:-1]):
                currel.append(rel[index]+ rel[index+1])
            currel.append(1)
            rel=currel
        return rel

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/pascals-triangle-ii/solution/wang-shi-wu-xu-zai-ti-qian-xing-zhi-shen-7p8c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

120：三角形最小路径和

回溯伤我千万遍，我待回溯如初恋

        n = len(triangle)
        dp = [10**4+1]*(n)
        dp[0] = triangle[0][0]
        for i in range(1,n):     #看第i 行
            for j in range(i,-1,-1):   #看第j列
                if j == 0:
                    dp[j] = triangle[i][j]+dp[0]
                else:
                    dp[j] = triangle[i][j] + min(dp[j],dp[j-1])
        return min(dp)


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/triangle/solution/hui-su-shang-wo-qian-mo-bian-wo-dai-hui-f493p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

121  卖股票最佳时机 

维持一个当前最大利润和前面的最小值。
如果当前值比最小值小 更新最小值
如果不小 就减去最小值看利润。
注意else 让我们包涵了股票一直跌的这种情况。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minpri = prices[0]
        maxpro = 0
        n = len(prices)
        for i in range(n):
            if prices[i] < minpri:
                minpri = prices[i]
            elif prices[i] - minpri > maxpro:
                maxpro = prices[i] - minpri
        return maxpro

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/wo-zhe-ge-elsejia-de-jian-zhi-jiu-shi-ti-fs2r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

122  卖股票最佳时机2 

遍历一遍
先找到一个比他后一天低的股票 买它！ 因为如果他后一天比他还低 肯定买那个更低的
再找到一个比他后一天高的股票 卖它！ 因为如果他后一天比他还高 肯定不卖啊
卖出之后重复上面步骤
就得到最大利润啦

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        def findnextpri(index):
            for i in range(index,n-1):
                if prices[i] < prices[i+1]:
                    return i
            return -1
        index = 0
        pri = 0
        while True:
            index = findnextpri(index)
            if index < 0:
                return pri
            for j in range(index,n):
                if j == n-1:
                    pri += prices[j] - prices[index]
                elif prices[j]>prices[j+1]:
                    pri += prices[j] - prices[index]
                    break
            index = j

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mei-xiang-dao-jie-guo-zhe-yao-hao-mo-mo-xji48/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

123： 二叉树最大路径和 

被94的人击败了时间 被95的人击败了空间

但至少是我自己想出来的。
我的dfs会返回两个值 一个是可以与当前结点连接的子树能达到的最大值
另一个是 不管连不连 子树上能达到的最大值 。
sumleft 就是左子树能和当前结点连接
,leftmax 左子树不一定能和当前结点连接。这一部分等于放弃人生前进希望的 就等着看有没有超过他的

怎么实现呢？
rootmax 是三种情况下的最大值：
1 左 + 根
2 右 + 根
3 左 + 右
这三种情况下 都可以继续往上扩展

maxsum 是 各种情况下最大值
除了上面三种外 还包括：
1 左右中
2 左
3 右
4 左子树的任意情况最大
5 右子树上任意最大
递归到根结点
就得到了 带上根节点能得到的最大的
空的时候返回-10000 意思就是直接放弃生活希望的那种

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root == None:
                return -10000,-10000
            sumleft,leftmax = dfs(root.left)
            sumright,rightmax = dfs(root.right)
            rootmax = max(sumleft+root.val,sumright+root.val,root.val)
            maxsum = max(sumleft+root.val,sumright+root.val,sumright+sumleft+root.val,root.val,sumleft,sumright,leftmax,rightmax)
            return rootmax,maxsum
        a,b = dfs(root)
        return b 

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/hahahahhahahbei-94de-ren-ji-bai-liao-shi-hn7h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。