😍 LeetCode Easy Collections III - 3 Problems

0231. Power of Two / 0118. Pascal's Triangle

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        
        if n <= 0: return False
        
        def pot(n):
            if n == 1:
                return True
            if n%2 == 1:
                return False
            
            return pot(n//2)
        
        return pot(n)

😍 0231) 큰 problem을 2로 계속 나누며 sub-problem으로 잘게 쪼개며 계속 문제를 풀어나가는 방식은 Recursion을 사용해야 함을 직관적으로 알 수 있다. 먼저 n == 1 / n%2 == 1 base case를 생각하고 / 그렇지 않다면 pot(n//2)로 잘게 쪼개어 문제를 풀어가면 OK

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]
        for i in range(1,numRows):
            row = []
            for j in range(0,i+1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    row.append(ans[i-1][j-1]+ans[i-1][j])
            ans.append(row)
        return ans

 

😍 0118) 공식에 맞게 dp table 채워나가면 된다.

---

0746. Min Cost Climbing Stairs

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [cost[0], cost[1]]
        for i in range(2, len(cost)):
            dp.append(min(dp[-1],dp[-2])+cost[i])
        return min(dp[-1],dp[-2])

 

😍 0746) DP 문제. 각 dp의 element는 해당 element 번째의 stair를 반드시 밟았다고 했을 때의 min cost로 정의. 그러면 i번째 계단을 밟았을 때의 min cost dp[i]는 앞서 바로 앞 계단을 밟았을 때와 / 바로 두번째 앞 계단을 밟았을 때의 cost 중 최솟값에 현재 계단을 밟았을 때의 값이다. 이후 쭉 dp를 업데이트 한 후, 맨 마지막 계단을 밟았을 때 / 맨 마지막 바로 앞 계단을 밟았을 때의 cost 중 최솟값으로 정답 리턴

---