본문 바로가기

Dynamic Programming9

LeetCode. Unique Paths Problem: 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? Example: -Cod.. 2020. 6. 30.
LeetCode 91. Decode Ways Problem: 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 "B.. 2020. 6. 21.
LeetCode. Pascal's Triangle Problem: Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. -Summary- Solved by dynamic programming approach (Below code is available from Leetcode solution) 1. The first and last element of each row is always 1. 2. Calculate inner elements by using and adding previous row elements. class Solution: def generate(self, num_rows): triangle = [] for row_num in ran.. 2020. 6. 21.
LeetCode. Largest Divisible Subset Problem: Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1: Input: [1,2,3] Output: [1,2] (of course, [1,3] will also be ok) Example 2: Input: [1,2,4,8] Output: [1,2,4,8] -Summary- 1. Sort the input nums list (*Sorti.. 2020. 6. 14.
LeetCode. House Robber [Dynamic Programming] Problem: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing t.. 2020. 6. 12.
5. Longest Palindromic Substring [Strings, dynamic programming] Problems: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd" Output: "bb" -Summary- Approach: Expand around the center 1. Two cases exist. - Palindrome with odd lengths of string (example: 'aba', 'abcba') --> where 1 character in th.. 2020. 6. 11.

티스토리툴바