Dynamic Programming - Michael's Blog

Word Break II

140. Word Break II 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. You may assume the dictionary does not contain duplicate words. Return all such possible sentences.

LintCode

Triangle

LintCode-109. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. Notice Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows

LintCode

Climbing Stairs

LintCode-111.Climbing Stairs 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? Example Given an example n=3 , 1+1+1=2+1=

LintCode

House Robber

LintCode-392.House Robber 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

LintCode

Maximum Subarray Difference

LintCode-45.Maximum Subarray Difference Given an array with integers. Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest. Return the largest difference. Notice: The subarray should contain at least one number Example: For [1, 2, -3, 1], return 6. Challenge: O(n) time

LintCode

Maximum Subarray

LintCode-41.Maximum Subarray Given an array of integers, find a contiguous subarray which has the largest sum. Notice: The subarray should contain at least one number. Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.