์ „์ฒด ๊ธ€

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

55. Jump Game

Description: Solution: From the last value, we are gonna update the goal pointer when i + nums[i] >= goal. The reason we do ">=" is that we can skip the index. The previous value of the last, we can skip that index. When the goal pointer reach out the nums[0], then it is True. Time Complexity: O(n)

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

62. Unique Paths

Description: Solution: row = [1] * n => The bottom row: [1, 1, 1, 1, 1, 1, 1] We start from (n-2) with reverse order. When we complete the second row[7, 6, 5, 4, 3, 2, 1], we update this newRow as row. Time Complexity: O(n*m) Space Complexity: O(n)

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

91. Decode Ways

Description: Solution: We should consider if the number is two digits case: 10, 20 Since A-Z is 26, 20-26 is the right range for decode. ex) s = "112" dp[3] = 1 dp[2] = 1 dp[1] = 1 + 1 = 2 dp[0] = 2 + 1 = 3 Space Complexity: O(1)

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

213. House Robber II

Description: Solution: We have to consider three cases: The first value of the array is the biggest number. Except the first value, try to find the maximum of the other values. Except the last value, try to find the maximum of the other values. Time Complexity: O(n) Space Complexity: O(1)

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

198. House Robber

Description: Solution: temp is for rob2. rob1 & rob2 is adjacent pointer. We are gonna compare n to (n - 1) + (n + 1)!

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

377. Combination Sum IV

Description: Solution: For this problem, we are gonna use hashmap. ex) nums = [1, 2, 3], target = 4 dp[0] = 1 dp[1] = dp[1] + dp[1-1] + dp[1-2] + dp[1-3] = 0 + 1 + 0 + 0 = 1 dp[2] = dp[2] + dp[2-1] + dp[2-2] + dp[2-3] = 0 + 1 + 1 + 0 = 2 dp[3] = dp[3] + dp[3-1] + dp[3-2] + dp[3-3] = 0 + 2 + 1 + 1 = 4 dp[4] = dp[4] + dp[4-1] + dp[4-2] + dp[4-3] = 0 + 4 + 2 + 1 = 7 โˆต dp[target] = 7 Time Complexity..

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

139. Word Break

Description: Solution: ex) s = "leetcode" wordDict = ["leet", "code"] In s, we start from the end of the string. dp[8] = True do[7] = False dp[6] = dp[5] = False dp[4] = True = dp[4 + 4] dp[3] = dp[2] = dp[1] = False dp[0] = True = dp[0 + 4] If dp[0] is True, it means we can break the string with wordDict!

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

300. Longest Increasing Subsequence

Descrtiption: Solution: We are gonna start from the last value of array. ex) nums = [1 ,2 ,4, 3] LIS[3] = 1 LIS[2] = max(1, 1 + LIS[3]) = 1 (nums[2] > nums[3]) LIS[1] = max(1, 1 + LIS[2], 1 + LIS[3]) = 2 LIS[0] = max(1, 1+1, 1+1, 1+2) = 3 So, the answer is 3. Time Complexity: O(n^2)

LeetCode ๐Ÿ”๏ธ/Interval

38. Meeting Rooms II

Description: Solution: We have two list: start & end. ex) start: [0, 5, 15] end: [10, 20, 30] We shift the start pointer when start[s] is less than end[e] => count += 1 We shift the end pointer when start[s] is equal or more thn end[e] => count -= 1 Time Complexity: O(nlogn) Space Complexity: O(n)

LeetCode ๐Ÿ”๏ธ/Interval

37. Meeting Rooms

Description: Solution: Note that the range should begin from index 1. Time Complexity: O(nlogn)

KB0129
To The Top ๐Ÿ—ป