leetcode 동적 기획

### leetcode 120               O(n**2)，     O(n) ###
###         
class Solution:
    def minimumTotal(self, triangle):
        f=triangle[-1]    #         f
        row = len(triangle)
        for i in range(row-2,-1,-1):
            for j in range(len(triangle[i])):
                f[j] = min(f[j],f[j+1])+triangle[i][j]
        return f[0]

### leetcode53     [E]      O(n)，     O(1)###
class Solution:
    def maxSubArray(self, nums):
        f = nums[0]
        maxsubarray=f
        for x in nums[1:]:
            f1 = max(f+x,x)   #     >0   ，  ；      
            f = f1
            if f1>maxsubarray:
                maxsubarray  = f1
        return maxsubarray

### leetcode62          O(m*n)      O(m*n) ###
class Solution:
    def uniquePaths(self, m, n):
        f = [[1 for _ in range(n)] for _ in range(m)] #            f ，         1,       
        for i in range(1,m):
            for j in range(1,n):
                f[i][j] = f[i-1][j]+f[i][j-1]  #  （1，1）  ，        
        return f[-1][-1]

### leetcode64            O(m*n)      O(n) ###
class Solution:
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        f = [grid[0][0]]*n
        for j in range(1,n):
            f[j] = f[j-1]+grid[0][j]
        for i in range(1,m):
            for j in range(n):
                if j==0:
                    f[j] += grid[i][j]
                else:
                    f[j] = min(f[j],f[j-1])+grid[i][j]
        return f[-1]

### leetcode63     II      O(m*n)      O(1) ###
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[0][0]==1:  #          ，  0   
            return 0
        else:
            obstacleGrid[0][0] = 1
        for j in range(1,n):      #      ，     ，    0，         
            if obstacleGrid[0][j]==1:
                obstacleGrid[0][j]=0
            else:
                obstacleGrid[0][j] = obstacleGrid[0][j-1]
        for i in range(1,m):    #      ，     ，    0，         
            if obstacleGrid[i][0]==1:
                obstacleGrid[i][0]=0
            else:
                obstacleGrid[i][0] = obstacleGrid[i-1][0]
        for i in range(1,m):   #  （1，1）     ，     ，    0，            
            for j in range(1,n):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j]+obstacleGrid[i][j-1]
        return obstacleGrid[-1][-1]

### leetcode91          O(n),     O(n)（    O(1)）###
class Solution:
    def numDecodings(self, s):
        n = len(s)
        if s[0] < '1':   #      0，   0
            return 0
        else:
            f = [1] * n # f            
        for i in range(1, n): 
            if i == 1:  #    2   ，     0，   0，           1-26   ，       0，     1
                if s[i] == '0':
                    if s[i - 1:i + 1] <= '26' and s[i - 1:i + 1] >= '1':
                        f[i] = 1
                    else:
                        return 0
                else:   #     0，     1-26   ，      2，      1
                    if s[0:2] > '26':
                        f[i] = 1
                    else:
                        f[i] = 2
            else: #              ，      0
                if s[i] == '0': #    0，        ，   1-26   ，   f[i-2],      0
                    if s[i - 1:i + 1] <= '26' and s[i - 1:i + 1] >= '1':
                        f[i] = f[i - 2]
                    else:
                        return 0
                else:  #     0，        ，   1-26   ，   f[i-2],       f[i-2]+f[i-1]
                    if s[i - 1:i + 1] > '26' or s[i - 1] == '0':
                        f[i] = f[i - 1]
                    else:
                        f[i] = f[i - 1] + f[i - 2]
        return f[-1]

### leetcode139          O(n**2)      O(n) ###
class Solution:
    def wordBreak(self, s, wordDict):
        n = len(s)
        f = [False]*(n+1)  #  f[i]  s[:i]     
        f[0] = True
        for i in range(1,n+1):
            for j in range(0,i):
                if f[j] and s[j:i] in wordDict: #         j   i-1   s[j:i]    ，f[i]  True
                    f[i] = True
        return f[-1]