leetcode 62(dp), 63, 64, 341(dfs)

62 https://leetcode.com/problems/unique-paths/

기초적인 dp문제이다. 0행과 0열은 전부 경우의 가지수가 1이고, 

n행 m열 = n-1행 m열의 경우의수 + n행 m-1열의 경우의수이다.

class Solution(object):
    def uniquePaths(self, m, n):
        dp = [[1 for j in xrange(m)] for i in xrange(n)]
        for i in xrange(1, n):
            for j in xrange(1, m):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]

63 https://leetcode.com/problems/unique-paths-ii/submissions/

위에랑 비슷한데 조건만 조금 더 추가되었다.

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[0 for j in xrange(n)] for i in xrange(m)]
        for i in xrange(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
        for i in xrange(n):
            if obstacleGrid[0][i] == 1:
                break
            dp[0][i] = 1
            
        for i in xrange(1, m):
            for j in xrange(1, n):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

64 https://leetcode.com/problems/minimum-path-sum/

이것도 위에랑 똑같은데 조건만 다르다. 처음에 최소 거리 개념으로 다익스트라를 생각했지만 굳이 다익스트라를 쓰지 않고도 위에 코드를 조금만 변경해서 푸는게 가능하다..

class Solution(object):
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for j in xrange(n)] for i in xrange(m)]
        dp[0][0] = grid[0][0]
        for i in xrange(1,m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in xrange(1,n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
             
        for i in xrange(1, m):
            for j in xrange(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[m-1][n-1]

341 https://leetcode.com/problems/flatten-nested-list-iterator/

dfs로 푼다. 안을 순회하면서 내부가 int면 추가, 그게 아니라 내부도 리스트면 스택에 다시 넣는다.

class NestedIterator(object):
    def __init__(self, nestedList):
        self.stack = nestedList[::-1]
        self.flattened_list = []
        while self.stack:
            p = self.stack.pop()
            if p.isInteger():
                self.flattened_list.append(p.getInteger())
            else:
                for pp in p.getList()[::-1]:
                    self.stack.append(pp)

    def next(self):
        return self.flattened_list.pop(0)

    def hasNext(self):
        return True if self.flattened_list else False