leetcode 509, 1137(피보나치), 746(계단, dp), 698(dfs)

509 leetcode.com/problems/fibonacci-number/
알고리즘 공부 시작하는 처음에 가장 먼저 배우는 쉬운거

class Solution(object):
    def fib(self, n):
        if n == 0:
            return 0
        f = [0] * (n+1)
        f[1] = 1
        for i in xrange(2, n + 1):
            f[i] = f[i-1] + f[i-2]
        return f[n]

복습용으로 읽어보는게 더 좋다 : leetcode.com/problems/fibonacci-number/discuss/215992/Java-Solutions

 

1137 leetcode.com/problems/n-th-tribonacci-number/

위랑 똑같음.

class Solution(object):
    def tribonacci(self, n):
        #n = 2
        if n == 0:
            return 0
        elif n == 1:
            return 1
        f = [0] * (n+1)
        f[1] = 1
        f[2] = 1
        for i in xrange(3, n + 1):
            f[i] = f[i-1] + f[i-2] + f[i-3]
        return f[n]

746 leetcode.com/problems/min-cost-climbing-stairs/

기초적인 dp문제 2. 백준의 www.acmicpc.net/problem/2579 와 비슷하다.

class Solution(object):
    def minCostClimbingStairs(self, cost):
        #cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
        n = len(cost)
        if n == 1:
            return cost[0]
        dp = [0] * n
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in xrange(2, n):
            dp[i] = cost[i] + min(dp[i-2], dp[i-1])
        return min(dp[n-1], dp[n-2])

698 leetcode.com/problems/partition-to-k-equal-sum-subsets/

dfs문제이다. n개의 리스트를 합이 동일한 k개의 리스트로 나눌수 있는지 물어보는 문제인데

1. 리스트 전체합 / k가 나머지없이 나누어 떨어지면 가능한거니 안 나누어 떨어지는 경우 제외

2. 모든 경우의 수 dfs탐색.

처음에 iterative하게 짰었는데 방문한 곳을 표시하는 visited를 매번 복사해서 집어넣어야 하다 보니 시간초과가 걸려서 재귀적으로 짰다.

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        # nums = [1,1, 1,1, 1,1, 1,1, 1,1]
        # k = 5
        # nums = [10, 10, 10, 7, 7, 7, 7, 7, 7, 6, 6, 6]
        # k = 3
        #nums = [780, 935, 2439, 444, 513, 1603, 504, 2162, 432, 110, 1856, 575, 172, 367, 288, 316]
        #k = 4
        num_sum = sum(nums)
        if num_sum % k != 0:
            return False
        target_subsum = num_sum / k
        visited = {}
        def DFS(k, index, cur_sum):
            if k == 0:
                return True
            if cur_sum == target_subsum:
                return DFS(k-1, 0, 0)
            for i in xrange(index, len(nums)):
                if not visited.get(i, False) and cur_sum + nums[i] <= target_subsum:
                    visited[i] = True
                    if DFS(k, i+1, cur_sum+nums[i]):
                        return True
                    visited[i] = False
            return False
            
        return DFS(k, 0, 0)

오랫만에 쉬운문제들 복습 겸 하니까 힐링되는듯