This is from leetcode, Best Time to Buy and Sell Stock IV. 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 at most k transactions. The answer is to use dynamic programming by local and global 2-dimension array to implement… Read More »
Problem description: Number of coins lined up, two persons take turn to pick up coins from both ends, what is the maximum total sum of money first person can pick? This post is to response to junmin‘s code. This one is a good one for dp. I wrote it in recursive way before. The formula for this… Read More »
This problem is from careercup. http://www.careercup.com/question?id=5725584103571456 Given a number “n”, find the least number of perfecet square numbers sum needed to get “n”. Exmaple: n=12, return 3 (4+4+4)=(2^2+2^2+2^2) NOT (3^2+1+1^2+1^2) n=6, return 3(4+1+1)=(2^2+1^2+1^2) At first sight, I thought this could be resolved by greedy method: round(sqrt(12))=3, remainder=3; round(sqrt(3))=1, remainder=2; round(sqrt(2))=1, remainder=1; But this won’t give out a… Read More »
I got this problem from Junmin: link. Problem: given a list of words and a window size of w, how to split them into multiple lines so that the fewest lines are used if possible. Example: w = 10, input: “given a list of words and a window size of w” potential optimal alignment: given a list… Read More »
This problem is from G4G link. It is a pratice for DP. Problem Description: Given N jobs where every job is represented by following three elements of it. 1) Start Time 2) Finish Time. 3) Profit or Value Associated. Find the maximum profit subset of jobs such that no two jobs in the subset overlap.… Read More »
Problem: Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are: 1) Decrement with cost = 1 2) Delete an element completely from the array with cost = value of element For example, input array is [10, 3, 11, 12]. The sorted array with minimum… Read More »
This problem frustrates me for a long time. Yesterday, I finally comprehended. Cheers! Problem: Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number k. If the array before adjustment is A, the array after adjustment is B, you should minimize the sum… Read More »
Problem description: There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is… Read More »
Problem description: Assume in x-coodinate, there are cities. The city i locates at xi position, and has pi people. Now people in those cities want to find a place to have a meeting. We should find the location l, where it spend least cost for all people(make the following formula smallest). We know how to find… Read More »