Tag Archives: DP

  1. 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

  2. 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

  3. 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

  4. Regular Expression/Wildcard Matching

    Leave a comment

    May 5, 2017 by oneOokay

    Regular Expression Matching Wildcard Matching Regular Expression Matching: Implement regular expression matching with support for ‘.’ and ‘*’. ‘.’ Matches …
    Continue reading

  5. 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

  6. Decode Ways

    Leave a comment

    February 21, 2017 by oneOokay

    A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ -> 1 ‘B’ -> …
    Continue reading

  7. Longest Increasing Subsequence

    Leave a comment

    December 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