动态规划算法详解及典型问题求解

# 动态规划算法详解及典型问题求解
## 动态规划概述
- 定义
  - 优化多阶段决策问题的方法
- 基本原理
  - 最优性原理
    - 最优解可由其子问题的最优解构成
  - 无后效性
    - 决策一旦做出，未来的决策不受影响
  - 有重叠子问题
    - 多个子问题重复计算
## 典型问题求解
### 求解斐波那契数列
- 递归方法
  - 时间复杂度高
  - 存在大量重复计算
- 动态规划方法
  - 使用dp数组
  - 记录中间结果
### 求解整数拆分问题
- 问题描述
  - 正整数n的拆分
  - 最大数为k的拆分
- 动态规划解法
  - 状态f(n, k)定义
    - 递推关系
### 求解最大连续子序列和问题
- 问题描述
  - 整数序列中的最大和
- 动态规划解法
  - dp数组记录
  - 以当前元素结尾的最大和
### 求解三角形最小路径问题
- 问题描述
  - 从顶部到底部的最小路径和
- 动态规划解法
  - dp数组记录
  - 从顶部到当前位置的最小路径和
### 求解最长公共子序列问题
- 问题描述
  - 两个字符序列的最长公共子序列
- 动态规划解法
  - dp数组记录
  - 最长公共子序列长度
### 求解最长递增子序列问题
- 问题描述
  - 无序整数序列中的最长递增子序列长度
- 动态规划解法
  - dp数组记录
  - 以当前元素结尾的最长递增子序列长度
### 求解编辑距离问题
- 问题描述
  - 字符串A转换为B的最少操作次数
- 动态规划解法
  - dp数组记录
  - 转换A的前i个字符和B的前j个字符的最少操作
### 求解0/1背包问题
- 问题描述
  - 选择物品使总价值最大
- 动态规划解法
  - dp数组记录
  - 背包剩余容量r的最优价值
### 求解完全背包问题
- 问题描述
  - 选择任意数量物品使总价值最大
- 动态规划解法
  - dp数组记录
  - 从前i个物品中选出重量不超过j的最大价值
### 求解资源分配问题
- 问题描述
  - 有限资源分配给多个使用者
- 动态规划解法
  - dp数组记录
  - 考虑前i个使用者的最优收益
### 求解会议安排问题
- 问题描述
  - 选择兼容会议订单
- 动态规划解法
  - dp数组纪录
  - 前i个订单中所有兼容订单的最长时间
## 滚动数组
- 定义
  - 特殊处理数组下标以节省存储空间
- 应用示例
  - 斐波那契数列
  - 0/1背包问题