dynamic programming - Post, Code and Quiet Time.

Post, Code and Quiet Time.

Sign in Subscribe

dynamic programming

A collection of 10 posts

Word Break II

Question Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Example Gieve s = lintcode, dict = ["de", "ding", "co", "code", "lint"]. A solution is ["lint code", "lint co de"

Word Break

Question http://www.lintcode.com/en/problem/word-break/ Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = "lintcode", dict = ["lint", "code"]. Return true because "lintcode" can be break as "lint

dynamic programming

Unique Paths III

Question http://www.lintcode.com/en/problem/unique-paths-iii/ Follow up for "Unique Paths II": https://acm.errong.win/uniquepathsii/ Now each grid contains a value, so each path also has a value. Find the sum of all the unique values paths. Example For example, [ [1,1,2], [1,2,3]

dynamic programming

Unique Paths II

Question http://www.lintcode.com/en/problem/unique-paths-ii/ Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. Example For example, There is

dynamic programming

Unique Paths

Question http://www.lintcode.com/en/problem/unique-paths/ A robot is located at the top-left corner of a m x n grid. 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. How many

dynamic programming

Maximum Subarray III

Question: http://www.lintcode.com/en/problem/maximum-subarray-iii/ Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum. Answer localMax[i][j], means the maximum sum we can get while

dynamic programming

Wildcard Matching

Question: http://www.lintcode.com/en/problem/wildcard-matching/ Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Answer: class Solution

dynamic programming

House Robber II

Question: http://www.lintcode.com/en/problem/house-robber-ii/ After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the

dynamic programming

House Robber

Question: 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 it will

dynamic programming

Maximal Square

Question: http://www.lintcode.com/en/problem/maximal-square/ Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area. Example For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1