DP
-
[LeetCode] Word Break II알고리즘 2019. 12. 19. 17:07
문제 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = "catsanddo..
-
[LeetCode] Word Break알고리즘 2019. 12. 19. 03:38
문제 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = "leetcode", wordDict = ["leet", "..
-
[LeetCode] Pascal's Triangle알고리즘 2019. 12. 4. 17:03
문제 Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] Approach 이전 줄의 원소를 더해 다음 줄을 만들면 된다 굳이 따지자면 DP? Code https://github.com/chi3236/algorithm/blob/master/LeetCode_Pascal'sTriangle.cpp chi3236/algorithm Co..
-
[LeetCode] Decode Ways알고리즘 2019. 11. 25. 18:26
문제 A message containing letters from A-Z is being encoded to numbers using the following mapping:'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 ..
-
[LeetCode] Largest Rectangle in Histogram알고리즘 2019. 11. 20. 18:05
문제 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit. Example: Input: [2,1,5,6,2,3] Output: 10 Approach i번째 막대에서 가장 큰 직사각형을 만드려면 i번째 막..
-
[LeetCode] Climbing Stairs알고리즘 2019. 11. 3. 23:04
문제 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb t..
-
[LeetCode] Unique Paths알고리즘 2019. 11. 3. 03:43
문제 Share A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there? Note: m and n..
-
[LeetCode] Jump Game알고리즘 2019. 11. 1. 23:34
문제 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: [3,2,1,0,4] Output: fals..