본문 바로가기

다이나믹프로그래밍26

[leetcode 309] Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After.. 2020. 10. 7.
[leetcode 322] Coin Change You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanati.. 2020. 10. 7.
[leetcode 338] Counting Bits 주어진 num까지 각각의 숫자를 이진수로 변환시켰을 때 1의 개수를 기록한 배열을 return Example 1: Input: 2 Output: [0,1,1] Example 2: Input: 5 Output: [0,1,1,2,1,2] ex2에서 0부터 5까지 각각을 이진수로 변환 0, 1, 10, 100 ... 그 때 1의 숫자를 세서 배열에 저장한다. 풀이 - dp - dp 치곤 쉬웠다. - 표를 적다보면 규칙이 발견된다. 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 2 1 2 2 3 1 2 2 3 2 1)2의 제곱수는 무조건 1이다. 2) 2의제곱수 사이에 있는 수는( 2 2020. 10. 7.
[leetcode 416] Partition Equal Subset Sum Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note: Each of the array element will not exceed 100. The array size will not exceed 200. Example 1: Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2: Input: [1, 2, 3, 5].. 2020. 10. 6.

티스토리툴바