动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果
动态规划有自底向上（递推）和自顶向下（记忆化递归）两种解决问题的方式
「动态规划」 - 学习计划
无后效性特点：一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，求解问题的过程形成了一张有向无环图
动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量
一、爬楼梯
递归式：f(n) = f(n - 1) + f(n - 2) , f(1) = 1, f(2) = 2, f(0) = 0
结束条件以及递归过程都可由递归式得出
同高度阶梯被计算多次的递归解法
class Solution {
public int climbStairs(int n) {
if(n > 1) {
return climbStairs(n -1) + climbStairs(n - 2);
}
return 1;
}
}
记忆递归（将计算过的高度阶梯保存到记忆数组）
class Solution {
//记忆递归
public int climbStairs(int n) {
if(n == 1) {//防止数组下标越界的特殊处理
return 1;
}
int[] memory = new int[n + 1];
memory[1] = 1;
memory[2] = 2;
return climbCount(memory, n);
}
private int climbCount(int[] memory, int n) {
if(memory[n] != 0) {
return memory[n];
}
memory[n] = climbCount(memory, n -1) + climbCount(memory, n - 2);
return memory[n];
}
}
这个视频讲得非常好 ： 爬楼梯
动态规划解法
动态规划的转移方程：f(x)=f(x−1)+f(x−2)
边界条件：f(0)=1，f(1) = 1。枚举x，得出计算结果说明边界可用
class Solution {
public int climbStairs(int n) {
if (n == 1)
return 1;
if (n == 2)
return 2;
int[] climb = new int[n + 1];
climb[1] = 1;
climb[2] = 2;
for (int i = 3; i <= n; i++) {
climb[i] = climb[i - 1] + climb[i - 2];
}
return climb[n];
}
}
- 优化：使用滚动数组
class Solution {
public int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}
可以用动态规划的问题都能用递归
从子问题入手，解决原问题，分两种做法：自顶向下和自底向上
前者对应递归，借助函数调用自己，是程序解决问题的方式，它不会记忆解
后者对应动态规划，利用迭代将子问题的解存在数组里，从数组0位开始顺序往后计算
对比：
- 递归的缺点在于包含重复的子问题（没有加记忆化的情况下）
- 动态规划的效率更高
DP局限性
DP 相比于 递归，有时候不太好理解，或者边界情况比较难确定
必须是一步步邻接的，连续地计算
加入了记忆化的递归，就灵活很多，它在递归基础上稍作修改，往往更好理解，也少了局限性，不好用DP时一定能用它
比如有时候要求出达到某个结果的路径，递归（DFS）回溯出路径，显然更有优势
二、打家劫舍
是否可以使用动态规划：可以将问题分为更小的问题（子问题）
写出子问题的递推关系：最难的一步
- 递归式：f(n) = MAX(f(n - 1) , f(n - 2) + nums[n - 1])
- n：被偷的第n号房子（从1开始），最大为数组的长度（也是最后一个房
- f(n - 1)：偷前一个房子，当前n号房子不偷
- f(n - 2) + nums[n - 1]：偷前面的前面的房子，还有当前n号房子
- 取两者最大值
- 递归结束：偷n小于等于0的房子
- 普通递归（超时）
class Solution {
public int rob(int[] nums) {
return robMax(nums, nums.length);
}
private int robMax(int[] nums, int n) {
if(n <= 0) {
return 0;
}
return Math.max(robMax(nums, n - 1), robMax(nums, n - 2) + nums[n - 1]);
}
}
- 记忆递归
class Solution {
//记忆递归
public int rob(int[] nums) {
int[] memory = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
memory[i] = -1;
}
return robMax(nums, nums.length, memory);
}
private int robMax(int[] nums, int n, int[] memory) {
if(n <= 0) {
return 0;
}
if(memory[n - 1] == -1) {
memory[n - 1] = Math.max(robMax(nums, n - 1, memory), robMax(nums, n - 2, memory) + nums[n - 1]);
}
return memory[n - 1];
}
}
动态规划解法
动态规划的转移方程：f(x)=MAX（f(x − 1), f(x − 2) + nums[x - 1]）
计算偷 x 个 房子 的最大值（x是从1开始算，数组下标从0）
边界条件：f(0)=1，f(1) = nums[0]。枚举x，得出计算结果说明边界可用
class Solution {
public int rob(int[] nums) {
int length = nums.length;
int[] ans = new int[length + 1];//多一位，存放初始条件 f(0) = 0、f(1) = nums[0]；最后一位是答案
int i = 1;//nums数组的下标
ans[i] = nums[0];//题目给出条件：nums至少一个元素
for(; i < length; i++) {
ans[i + 1] = Math.max(ans[i], ans[i - 1] + nums[i]);//计算 偷（本次循环有）i + 1个房子的最大值
}
return ans[i];
}
}
-
优化：使用滚动数组
class Solution { public int rob(int[] nums) { int p = 0; int q = nums[0]; int ans = q; for(int i = 1; i < nums.length; i++) { ans = Math.max(q, p + nums[i]); p = q; q = ans; } return ans; } }
三、三角形最小路径和
递归式总是难倒人：
若定义 f(i, j)f(i,j) 为 (i, j)(i,j) 点到底边的最小路径和，则易知递归求解式为:
f(i, j) = min(f(i + 1, j), f(i + 1, j + 1)) + triangle[i] [j]
记忆递归写法
为什么使用Integer的二维数组：初始每个元素全为空，如果是没有计算过的，那么判断条件就是空值，再将结果放入，将不为空
使用int数组：初始化为0，那么计算中可能得到的是0，将其放入，0这个值不利于判断是否已经计算
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
Integer[][] memory = new Integer[triangle.size()][triangle.get(triangle.size() - 1).size()];
return minTotal(triangle, 0, 0, memory);
}
private int minTotal(List<List<Integer>> triangle, int i, int j, Integer[][] memory) {
if(i >= triangle.size()) {
return 0;
}
if(memory[i][j] == null) {
memory[i][j] = triangle.get(i).get(j) + Math.min(minTotal(triangle, i + 1, j, memory), minTotal(triangle, i + 1, j + 1, memory));
}
return memory[i][j];
}
}
从底向上递推，ans记录每一行的每个元素向下走的最小路径和
无论是走哪一条路都可以回到ans[0] [0]：即使链表第一行的第一个元素
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
//ans作为dp数组
int n = triangle.size();
int[][] ans = new int[n + 1][n + 1];
int i = n - 1;
while(i >= 0) {
for(int j = 0; j <= i; j++) {
ans[i][j] = Math.min(ans[i + 1][j], ans[i + 1][j + 1]) + triangle.get(i).get(j);
}
i--;
}
return ans[0][0];
}
}
优化：
手动模拟一遍上述算法，会发现ans存在累加现象：第n层的值会加到第 n - 1层
那么只用使用 O(n) 的额外空间（n 为三角形的总行数）就能储存各行加起来的结果
ans = new int[triangle.size()]
其中，ans[0] ：把下面的每一行都取了最小值添加
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
//ans作为dp数组
int n = triangle.size();
int[] ans = new int[n + 1];
int i = n - 1;
while(i >= 0) {
for(int j = 0; j <= i; j++) {
ans[j] = Math.min(ans[j], ans[j + 1]) + triangle.get(i).get(j);
}
i--;
}
return ans[0];
}
}
