Tag Archives: DP

Maximum Sum of 3 NonOverlapping Subarrays
Leave a commentOctober 15, 2017 by oneOokay
In a given array nums of positive integers, find three nonoverlapping subarrays with maximum sum. Each subarray will be of size k, and …
Continue reading 
265. Paint House II
Leave a commentSeptember 28, 2017 by oneOokay
here are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house …
Continue reading 
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 
Wildcard Matching/Regular Expression
Leave a commentMay 5, 2017 by oneOokay
Regular Expression Matching Wildcard Matching Wildcard matching:Implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single …
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