04_dynamic_programming.md

Table of Contents generated with DocToc

• dynamic programming 动态规划
  • 特征
  • 场景
  • 分类
    • 线性 DP
      • 1 编辑距离
      • 2 LCS 最长公共子序列--非连续
    • 区间 DP
      • 最长回文子序列
    • 状态机 DP
    • 树形 DP
    • 2 爬台阶
    • 3 找零钱
    • 4 0-1 背包
    • 5 机器人走法
    • 6 打家劫舍
    • 8 最长递增子序列
  • 解题思路
  • 参考

dynamic programming 动态规划

将大规范的问题转换成小规模的问题，并且缓存中间结果。 动态规范 = 分治递归 + 记忆存储

特征

leetcode原题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题。在青蛙跳阶问题中：

• f(n-1)和f(n-2) 称为 f(n) 的最优子结构
• f(n)= f（n-1）+f（n-2）就称为状态转移方程
• f(1) = 1, f(2) = 2 就是边界啦
• 比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。

动态规划的思路：

• 穷举分析
• 确定边界
• 找出规律，确定最优子结构
• 写出状态转移方程

场景

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

分类

• 线性动态规划：具有「线性」阶段划分的动态规划方法统称为线性动态规划（简称为「线性 DP」）

• DP 状态机：往往是强调某一个阶段和上一个阶段之间的联系，且一个阶段里面有多种状态（比如说“有”和“无”）。

• 区间 DP: 从小区间转移到大区间

• 树形 DP

线性 DP

1 编辑距离

s = horse t = ros

dfs(i,j)=

• s[i]=s[j]: dfs[i-1,j-1]
• s[i]!=s[j]: min(dfs(i,j-1),dfs(i-1,j),dfs(i-1,j-1))+1

2 LCS 最长公共子序列--非连续

• 子数组/子串 subarray/substring 连续
• 子序列 subsequence 非连续


s: 第一个字符串， 长度为 n t: 第二个字符串， 长度为 m

子问题：都选==都不选

dfs[i,j]=

• max(dfs[i-1,j-1]+1) s[i]=t[j]
• max(dfs[i-1,j],dfs[i,j-1]) s[i]!=t[j]


区间 DP

最长回文子序列

思路一： s 与 s反转后的 LCS(最长公共子序列)

• S1=eacbba
• S2=abbcae

思路二： 从两侧缩小问题规模 

因为 最左e != 最右a：所以不能同时选 

dfs(i,j)=

• dfs(i+1,j-1)+2 s[i]=s[j]
• max(dfs(i+1,j),dfs(i,j-1)) s[i]!=s[j]

递归边界

• 如果剩余一个字母,为回文 dfs(i,i)=1
• 两个字母相同时,比如bb dfs(i,i+1)-->dfs(i+1,i)

状态机 DP

树形 DP

二叉树的直径

二叉树的最大路径和

相邻字符不同的最长路径

打家劫舍III

监控二叉树

蓝色=min(左蓝,左黄,左红)+min(右蓝,右黄,右红)+1

黄色=min(左蓝,左红)+min(右蓝,右红)+1

红色=min(左蓝,右红)+min(右红,右蓝)+min(左蓝,右蓝)

2 爬台阶

要么n-1台阶上去，要么n-2台阶上去

3 找零钱

分治递归

递归实现

递推实现

4 0-1 背包

背包理论基础01背包-1.md

• 最多装 capacity, 求最大值 dfs(i,c)=max(dfs(i-1.c),dfs(i-1,c-w[i],v[i])
• 正好装 capacity, 求方案数量 dfs(i,c)=dfs(i-1,c)+dfs(i-1,c-w[i])
• 至少装 capacity, 求最小值 dfs(i,c)=min(dfs(i-1.c),dfs(i-1,c-w[i],v[i])

完全背包：物品可以重复选

• dfs(i,c)=max(dfs(i-1.c),dfs(i,c-w[i],v[i])

5 机器人走法

递归算法：优化代码

递推算法

6 打家劫舍

加缓存优化后

可以看到 01->2 ,12->3, 32->4, 所以留下归

从后面开始算: dfs[i] = max(dfs(i-1), dfs(i-2)+nums[i])

数组转换--> f[i]=max(f[i-1],f[i-2]+num[i])

因为防止负数 --> f[i+2]=max(f[i+1],f[i]+num[i])

8 最长递增子序列

思路一：选 或 不选， 从后面往前

思路二：枚举选哪个，选比当前小的前面数据

dfs[i]= max{dfs[j}+1 j<i 且 nums[j]<nums[i]

思路三：LIS = nums 与排序去重后 nums 的 LCS

思路四：交换状态与状态值

g[i] 表示 长度为 i+1 的IS 的末尾元素的最小值

解题思路

优化前代码: 递归自顶向下

优化后代码：递推自底向上

节省空间：交替滚动

 翻译成递推 f[i][j] =

• 0 i>j

• 1 i=j

• f[i+1][j-1]+2 s[i]=s[j]

• max(f[i+1][j],f[i+1][j-1]) s[i]!=s[j]

• 因为需要从 f[i+1]->f[i],所以 i 逆序，

• 因为从 s[i][j-1]->f[i][j], 所以 j 正序

答案是 f[0][n-1]

参考

• 动态规划详解
• 灵茶山艾府DP算法分类及题目