Tag Archives: DP

  1. Maximum Sum of 3 Non-Overlapping Subarrays

    Leave a comment

    October 15, 2017 by oneOokay

    In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size k, and …
    Continue reading

  2. 265. Paint House II

    Leave a comment

    September 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

  3. Combination Sum IV

    Leave a comment

    September 16, 2017 by oneOokay

    其他的Combination Sum Combination Sum IV Given an integer array with all positive numbers and no duplicates, find the number of …
    Continue reading

  4. 01 Matrix

    Leave a comment

    June 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

  5. Edit Distance

    Leave a comment

    May 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

  6. Wildcard Matching/Regular Expression

    Leave a comment

    May 5, 2017 by oneOokay

    Regular Expression Matching Wildcard Matching Wildcard matching:Implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single …
    Continue reading

  7. 01背包及优化

    Leave a comment

    March 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的0-10代表此时背包能够装的总重量W 空的格子里面([n][W])填:当背包能装的总重量为W的时候,考虑装前n个物品(包含n)所能够得到的最大的总价值. Object NO# Weight …
    Continue reading