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)
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)
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)
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)
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!
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..
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)..