Tag Archives: DP

01 Matrix
Leave a commentJune 20, 2017 by oneOokay
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance …
Continue reading 
Edit Distance
Leave a commentMay 25, 2017 by oneOokay
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation …
Continue reading 
Regular Expression/Wildcard Matching
Leave a commentMay 5, 2017 by oneOokay
Regular Expression Matching Wildcard Matching Regular Expression Matching: Implement regular expression matching with support for ‘.’ and ‘*’. ‘.’ Matches …
Continue reading 
01背包及优化
Leave a commentMarch 16, 2017 by oneOokay
01背包:(对于一个物品,取或者不取(取0次和取1次)) 一个背包能够给装总重量为W的物品 总共N个物品: 第i个物品的重量为w[i] 第i个物品的价值为v[i] 每个物品可取可不取.(取1次或取0次) 求:背包所能够装的所有物品的最大的总价值为多少. 二维数组 空间优化:一维数组 值的初始化: (背包恰好装满的情况下,背包内所有物品的最大的总价值为多少) 常数的优化: 对于物品进行排序优化 输出路径 假设背包能够装重量为10, 总共5个物品:#0#4.重量为:{2,2,6,5,4},价值为:{6,3,5,4,6}.开始填这样一个表: header的010代表此时背包能够装的总重量W 空的格子里面([n][W])填:当背包能装的总重量为W的时候,考虑装前n个物品(包含n)所能够得到的最大的总价值. Object NO# Weight …
Continue reading 
Decode Ways
Leave a commentFebruary 21, 2017 by oneOokay
A message containing letters from AZ is being encoded to numbers using the following mapping: ‘A’ > 1 ‘B’ > …
Continue reading 
Longest Increasing Subsequence
Leave a commentDecember 1, 2016 by oneOokay
Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, …
Continue reading 
Word Break
Leave a commentNovember 6, 2016 by oneOokay
Given a string s and a dictionary of words dict, determine if s can be segmented into a spaceseparated sequence …
Continue reading