Dynamic Programming - Michael's Blog

Dynamic Programming

A collection of 8 posts

Combination Sum IV

377. Combination Sum IV [https://leetcode.com/problems/combination-sum-iv/] Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. Example: nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1)

Split Array Largest Sum

410. Split Array Largest Sum [https://leetcode.com/problems/split-array-largest-sum/] Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Note: If n is the length

Word Break II

140. Word Break II [https://leetcode.com/problems/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.

Triangle

LintCode-109. Triangle [http://www.lintcode.com/en/problem/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

Climbing Stairs

LintCode-111.Climbing Stairs [http://www.lintcode.com/en/problem/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

House Robber

LintCode-392.House Robber [http://www.lintcode.com/en/problem/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

Maximum Subarray Difference

LintCode-45.Maximum Subarray Difference [http://www.lintcode.com/en/problem/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,

Maximum Subarray

LintCode-41.Maximum Subarray [http://www.lintcode.com/en/problem/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,