经典题型

Kevin2li大约 1 分钟

经典题型

动态规划类常见题目可以主要分为一维DP、二维DP、分割类问题、子序列问题、背包问题、字符串编辑问题、股票交易问题等。

一维DP

  1. 爬楼梯问题
image.png
image.png
  1. 打家劫舍问题
image.png
image.png
  1. 打家劫舍 II(环形)
image.png
image.png

二维DP

  1. 最小路径和
image.png
image.png
  1. 01矩阵
image.png
image.png
  1. 最大正方形面积
image.png
image.png

分割类问题

  1. 完全平方数open in new window
image.png
image.png
  1. 解码方法open in new window
image.png
image.png
  1. 单词拆分open in new window
image.png
image.png
  1. 整数拆分open in new window
image.png
image.png
  • 状态说明
    dp[i]dp[i]表示整数i的拆分最大乘积
  • 状态转移公式
    dp[i]=max(dp[i],k∗dp[i−k],k∗(i−k)),k=1...(i−1)dp[i] = max(dp[i], k*dp[i-k], k*(i-k)), k=1...(i-1)

子序列问题

  1. 最长递增子序列
image.png
image.png
  1. 最长公共子序列
image.png
image.png

背包问题

image.png
image.png

0-1背包和完全背包是最常见的两种类型。

  1. 分割等和子集
image.png
image.png
  1. 1和0
image.png
image.png
  1. 零钱兑换
image.png
image.png
  1. 目标和
image.png
image.png

字符串编辑

  1. 编辑距离
image.png
image.png
  1. 只有两个键的键盘
image.png
image.png
  1. 正则表达式匹配
image.png
image.png

股票交易

  1. 买卖股票的最佳时机
image.png
image.png
  1. 买卖股票的最佳时机 IV
image.png
image.png
  1. 最佳买卖股票时机含冷冻期
image.png
image.png
  1. 买卖股票的最佳时机含手续费
image.png
image.png