Basics

  • 考虑使用DP的情况
    • 求最大最小
    • 判断是否可行
    • 统计方案个数
  • 不使用DP的情况
    • 求出所有具体方案 而非 方案个数 (考虑DFS)
    • 输入是一个 集合 而不是 序列
    • 暴力算法复杂度已经是多项式级别
      • DP一般也就多项式级别，多用于优化 指数级别复杂度 (2^n, n!)
  • 四要素
    • 状态 state
    • 方程 function
    • 初始化 initialization
    • 答案 answer
  • DP类型
    • 坐标型 (10%)
    • 单序列 (30%)
    • 双序列 (30%)
    • 划分型 (10%)
    • 背包型 (10%)
    • 区间型 (10%)
  • 坐标型
    • state: f[x] 表示我从起点走到坐标x..., f[x][y] 表示我从起点走到坐标x, y
    • function: 研究走到 x, y 这个点的前一步
    • initialize: 起点
    • answer: 终点

  • 单序列

    • state: f[i] 表示前 i 个位置/数字/字符, 第 i 个

    • function: f[i] = f[j] ... j是i之前的一个位置

    • initialize: f[0]

    • answer: f[n]..

      • 一般answer是 f(n) 而不是f(n-1) 因为对于n个字符，包含前0个字符(空串)，前1个字符......前n个字符。

Problems

minimum path sum: http://www.lintcode.com/en/problem/minimum-path-sum/

unique path: http://www.lintcode.com/en/problem/unique-paths/

unique path ii: http://www.lintcode.com/en/problem/unique-paths-ii/

climbing stairs: http://www.lintcode.com/en/problem/climbing-stairs/

jump game: http://www.lintcode.com/en/problem/jump-game/

jump game ii: http://www.lintcode.com/en/problem/jump-game-ii/

longest increasing subsequence (LIS): http://www.lintcode.com/en/problem/longest-increasing-subsequence/

word break: http://www.lintcode.com/en/problem/word-break/

palindrome partitioning ii: http://www.lintcode.com/en/problem/palindrome-partitioning-ii/

longest common subsequence (LCS): http://www.lintcode.com/en/problem/longest-common-subsequence/

longest common substring

edit distance: http://www.lintcode.com/en/problem/edit-distance/

distinct subsequence: http://www.lintcode.com/en/problem/distinct-subsequences/

interleaving string: http://www.lintcode.com/en/problem/interleaving-string/

house robber: linear

house robber ii: circular

house robber iii: binary tree

•背包类:
•http://www.lintcode.com/problem/backpack/
•http://www.lintcode.com/problem/backpack-ii/
•http://www.lintcode.com/problem/minimum-adjustment-cost/
•http://www.lintcode.com/problem/k-sum/
•区间类:
•http://www.lintcode.com/problem/coins-in-a-line-iii/
•http://www.lintcode.com/problem/scramble-string/
•划分类:
•http://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv/•http://www.lintcode.com/problem/maximum-subarray-iii/

results matching ""

    No results matching ""