LeetCode ๐Ÿ”๏ธ/Dynamic Programming

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 ๐Ÿ”๏ธ/Dynamic Programming

332. Coin Change

Today, I solved coin chnage. Description: In this problem, we should find the fewest number of coins that make up that amount. Solution: This is the brute force solution. Let's say coin is [1, 3, 4, 5], and amount = 7. dp[0] is always "0" (because no need to coin to get to 0) dp[1] = 1 dp[2] = 2 dp[3] = 1 -> one 3coin dp[4] = 1 -> one 4coin dp[5] = 1 -> one 5coin dp[6] = 2 -> one 1coin + one 5co..

LeetCode ๐Ÿ”๏ธ/Dynamic Programming

70. Climbing Stairs

Today, I solved the climbing staris. Description: Solution: Let's say the example(n = 5). On the 4th stair, we have only 1 way to get 5th stair. On the 3rd stair, we have (1 + 1) ways to get 5th stair. On the 2nd stair, we have (2 + 1) ways to get 5th stair. In my code, we set (n-1)th stair as "one", and nth stair as "two." We shift those one and two until we get to 0(start point). (n-1) and (n)..

KB0129
'LeetCode ๐Ÿ”๏ธ/Dynamic Programming' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก