从斐波拉契数列说起

再贴一下斐波拉契数列的问题

已知斐波拉契数列的第一项和第二项分别为0和1,递推公式为$F(n)=F(n-1)+F(n-2)$,求第n项的值。

递归形式

上一篇中,我们从递推公式得到了下面递归形式的斐波拉契数列的解法, 并且发现它的效率是很低的。

1
2
3
4
int Fabric(int n){
if(n==0||n==1) return n;
return Fabric(n-1)+Fabric(n-2);
}

究其原因,是递归的过程中存在大量的重复计算(重叠子问题)。通过递归树我们可以明显地看出这一点:

上一篇也提到过可以通过某种方法消除重复计算,给递归树“剪枝” ——即使用备忘录。

使用备忘录

我们可以使用一个备忘录,把计算过的值都记下来,每次计算之前都判断一下这个值是否在备忘录中,这种方法就是记忆化搜索

这个备忘录可以是数组,也可以是哈希表。我们一般使用数组。

1
2
3
4
5
6
7
8
9
10
11
int Fabric_memo(int n,int* memo){
if(n<=1) return n;
if(memo[n]==0)
memo[n]=Fabric_memo(n-1,memo)+Fabric_memo(n-2,memo);
return memo[n];
}
int Fabric(int n){
int memo[n+1]={0};
int ans=Fabric_memo(n,memo);
return ans;
}

由于使用了一个记忆数组,所以空间复杂度从O(1)升到O(n),典型的以空间换时间,但是时间复杂度从O($2^n$)降到O(n),这波降维打击!

递推形式

上面的两种方法,说白了就是递归和对递归的优化。递归是自顶向下 去思考问题的:要计算F(n),就要计算F(n-1)和F(n-2),要计算F(n-1),就要计算F(n-2)和F(n-3)……

很显然,我们还可以自底向上 地迭代去解决这个问题:$F(2)=F(1)+F(0),F(3)=F(2)+F(1)……F(n)=F(n-1)+F(n-2)$。

和备忘录的方法同样地,我们使用一个数组来记录算过的值,但是使用循环:

1
2
3
4
5
6
7
int Fabric(int n){
if(n<=1) return n;
int DP[n]={1,1};
for(int i=2;i<n;i++)
DP[i]=DP[i-1]+DP[i-2];
return DP[n-1];
}

进一步可以发现,我们求解出某位的值的时候只需要知道其前两位的值,所以我们只需要3个数组空间,这样就把空间复杂度降到$O(1)$。

1
2
3
4
5
6
7
8
9
10
int Fabric(int n){
if(n<=1) return n;
int DP[3]={0,1,1};
for(int i=2;i<n;i++){
DP[0]=DP[1];
DP[1]=DP[2];
DP[2]=DP[0]+DP[1];
}
return DP[2];
}

总结

我们现在来总结一下上面三种方法:

  1. 递归形式很简洁、优美,可读性强;但是效率太低,存在太多的重复计算,实际上是一种暴力的方法
  2. 递归的同时使用记忆化搜索可以避免重复计算,实现降维打击。
  3. 在递归自顶向下的基础上,我们寻求自底向上的解法,这就是递推。自底向上的好处是我们更容易通过不同状态间的关系,将备忘录的大小降到常数

实际上,这个过程就是动态规划思想的来源。

动态规划

斐波拉契数列的结论

动态规划(Dynamic Programming)是运筹学中的一种方法,它的主要用途是求最值。

我们很容易想到,求最值的最简单方法就是暴力穷举,递归就是进行穷举的一种方法。但是,穷举的效率低下,动态规划的目标就是让我们优雅地穷举,提高穷举的效率。

优化的第一种思路是使用记忆化数组,通常称为memo数组 ;第二种思路是自底向上迭代,这时使用的数组通常称为DP数组 。DP数组的优点是可以在memo数组的基础上对空间进行优化,如从二维降到一维,一维降到常数等。

我们通常说的动态规划都是指的自底向上这种思路。


动态规划三要素

动态规划有三个要素:重叠子问题、最优子结构和状态转移方程

  1. 重叠子问题 是暴力递归效率低下的原因,也正是能使用动态规划对穷举进行优化的前提。

  2. 最优子结构 可以看成能使用递归进行穷举的前提。即一个问题可以分解为多个子问题,同时这个问题也是子问题的一个特例,并且这个问题的结果可以由其子问题得到。以斐波拉契数列为例,F(n)可以分解为子问题F(n-1)和F(n-2),同时F(n)也是当n=n时的一个特例,并且F(n)=F(n-1)+F(n-2)。

  3. 状态转移方程 就是解决这个问题如何由其子问题得到,这个问题的结果就是一个状态,确定一个状态的值就是状态参数。以斐波拉契数列为例,F(n)是一个状态,F(n-1)也是一个状态,n就是确定这个状态的状态参数。状态转移方程就是F(n)=F(n-1)+F(n-2)。


下面用具体的例子来体会动态规划的三要素。

打家劫舍

题目

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:输入:[1,2,3,1] 输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

我们还是先按照暴力递归的思路来思考这问题:对于一间房屋,我们要么选择偷,然后加上隔了一间的剩余房屋;要么就选择不偷,如下图所示:

递归的终止条件就是到了数组的末尾(后两位),所以代码如下:

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int rob(vector<int>& nums,int start=0) {
if(start==nums.size()-1) return nums.back();
if(start==nums.size()-2) return max(nums[start],nums.back());
int ans1=nums[start]+rob(nums,start+2);
int ans2=rob(nums,start+1);
return max(ans1,ans2);
}
};

但是因为暴力递归有太多的重复计算,OJ会判超时。所以接下来的改进是添加一个memo数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int rob_memo(vector<int>& nums,int* memo,int start){
if(start==nums.size()-1) return nums.back();
if(start==nums.size()-2) return max(nums[start],nums.back());
if(memo[start]==-1)
memo[start]=max(nums[start]+rob_memo(nums,memo,start+2)
,rob_memo(nums,memo,start+1));
return memo[start];
}
int rob(vector<int>& nums,int start=0) {
int memo[nums.size()];
for(int i=0;i<nums.size();i++) memo[i]=-1;
int ans=rob_memo(nums,memo,0);
return ans;
}
};
judge

然后我们再思考自底向上递推的方法,即动态规划。这时关键是确定状态转移方程:

  1. 如果只有一间,那么肯定选择要偷:$rob(1)=nums[0]$;

  2. 如果有两间,那么选择更大的那一间:$rob(2)=max(nums[0],nums[1])$;

  3. 如果有三间,要么选择第一间加第三间,要么选择第二间,即$rob(3)=max(rob(1)+nums[2],rob(2))$;
  4. 如果有四间,那么$rob(4)=max(rob(2)+nums[3],rob(3))$;
  5. ……

如果有n间,那么$rob(n)=max(rob(n-2)+nums[n-1],rob(n-1))$,即为状态转移方程。

从状态转移方程可以看出,要推导出一个状态,只需要知道这个状态的前两个状态,所以我们只需要构造一个三个int大小的DP数组储存前两个状态和现态即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()<=2)
return nums.size()==1?nums[0]:max(nums[0],nums[1]);
int len=nums.size();
int DP[3]={nums[0],max(nums[0],nums[1])};
for(int i=2;i<len;i++){
DP[2]=max(nums[i]+DP[0],DP[1]);
DP[0]=DP[1];
DP[1]=DP[2];
}
return DP[2];
}
};
judge


三角形的最小路径和

题目

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1:输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出:11
解释:如下面简图所示:
    2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

这道题我们尝试直接从动态规划入手。

我们先储存最后一行的所有值作为到最后一行每个点的最短距离;那么到h-1行的所有值,$DP(i)=min(DP(i),DP(i+1))+triangle[h-1][i]$,即为状态转移方程。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int len=triangle.size();
vector<int> DP=triangle[len-1];
for(int i=2;i<=len;i++)
for(int j=0;j<=len-i;j++)
DP[j]=triangle[len-i][j]+min(DP[j],DP[j+1]);
return DP[0];
}
};
judge