内容简介：动态规划本质依然是递归算法，只不过是满足特定条件的递归算法；动态规划是一个设计感比较强，艺术感比较强的一种算法设计思想。将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。通过计时我们会发现这个算法很慢，为什么这个解法效率这么低呢？当我们需要计算fib(5)时，它的递归树是：
动态规划本质依然是递归算法，只不过是满足特定条件的递归算法；动态规划是一个设计感比较强，艺术感比较强的一种算法设计思想。
什么是动态规划
定义
将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。
- 我们先解决小数据量的问题，之后层层递推来解决更大数据量的问题，通常这个过程就叫做动态规划。这个时间和记忆化搜索的时间复杂度是相当的，不过动态规划没有递归的调用，不需要额外调用和栈空间。
- 动态规划是一个设计感比较强，艺术感比较强的一种算法设计思想。
一个简单例子
#include <iostream>
#include <ctime>
using namespace std;
int num = 0;
int fib( int n ){
num ++;
if( n == 0 )
return 0;
if( n == 1 )
return 1;
return fib(n-1) + fib(n-2);
}
int main() {
num = 0;
int n = 42;
time_t startTime = clock();
int res = fib(n);
time_t endTime = clock();
cout<<"fib("<<n<<") = "<<res<<endl;
cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
cout<<"run function fib() "<<num<<"times."<<endl;
return 0;
}
复制代码
分析
通过计时我们会发现这个算法很慢，为什么这个解法效率这么低呢？当我们需要计算fib(5)时，它的递归树是：
从这个图可以看出这里面有大量的重复计算，我们怎样避免呢，我们可以在程序的外面做一个数组memo，其实memo[i]就记忆了第i个斐波那契数列。
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
vector<int> memo;
int num = 0;
// 记忆化搜索
int fib( int n ){
num ++;
if( n == 0 )
return 0;
if( n == 1 )
return 1;
if( memo[n] == -1 )
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
int main() {
num = 0;
int n = 42;
memo = vector<int>(n+1,-1);
time_t startTime = clock();
int res = fib(n);
time_t endTime = clock();
cout<<"fib("<<n<<") = "<<res<<endl;
cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
cout<<"run function fib() "<<num<<"times."<<endl;
return 0;
}
复制代码
我们采用一个memo数组来记忆，所以叫做记忆化搜索。记忆化搜索其实就是在递归的过程中添加计划化，是一种自上向下的解决问题，我们假设基本的问题已经解决了，我们已经会求fib(n-1)和fib(n-2)了，那么我们就能求第n个数了。
如果我们能自上而下解决问题，我们也能自下而上解决问题，只不过很多时候我们习惯于前者。
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
// 动态规划
int fib( int n ){
vector<int> memo(n+1, -1);
memo[0] = 0;
memo[1] = 1;
for( int i = 2 ; i <= n ; i ++ )
memo[i] = memo[i-1] + memo[i-2];
return memo[n];
}
int main() {
// 结果会溢出,这里只看性能
int n = 1000;
time_t startTime = clock();
int res = fib(n);
time_t endTime = clock();
cout<<"fib("<<n<<") = "<<res<<endl;
cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
return 0;
}
复制代码
第一个动态规划问题
leetcode 70. 爬楼梯
解题思路
我们来看一下递归的思路，把一个大的问题分解成小的问题。
代码实现（递归）
#include <iostream>
#include <vector>
using namespace std;
// 记忆化搜索
class Solution {
private:
vector<int> memo;
int calcWays(int n){
if( n == 0 || n == 1)
return 1;
if( memo[n] == -1 )
memo[n] = calcWays(n-1) + calcWays(n-2);
return memo[n];
}
public:
int climbStairs(int n) {
memo = vector<int>(n+1,-1);
return calcWays(n);
}
};
复制代码
代码实现（动态规划）
我们会发现和上面斐波那契一样，很轻易可以转化为动态规划解法。
#include <iostream>
#include <vector>
using namespace std;
// 动态规划
class Solution {
public:
int climbStairs(int n) {
vector<int> memo(n+1, -1);
memo[0] = 1;
memo[1] = 1;
for ( int i = 2; i <= n; i++ ) {
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
};
复制代码
相似问题
- leetcode 120
- leetcode 64
发现重叠子问题
leetcode 343. 整数拆分
解题思路
对于一个问题如果没有思路时，我们可以先考虑暴力解法。话句话说，我们使用什么样的方式，才能把正整数n的所有分割枚举出来，我们无法知道有几重循环，通常我们需要使用递归的手段。
暴力解法：回溯遍历将一个数做分割的所有可能性。O(2^n)
之所以递归树存在，是因为它有最优子结构
通过求子问题的最优解，可以获得原问题的最优解。
最优子结构
- 通过求子问题的最优解， 可以获得原问题的最优解
代码实现
实现1
#include <iostream>
#include <cassert>
using namespace std;
class Solution {
private:
int max3( int a , int b , int c ){
return max( a , max(b,c) );
}
// 将n进行分割(至少分割两部分), 可以获得的最大乘积
int breakInteger( int n ){
if( n == 1 )
return 1;
int res = -1;
for( int i = 1 ; i <= n-1 ; i ++ )
res = max3( res , i*(n-i) , i * breakInteger(n-i) );
return res;
}
public:
int integerBreak(int n) {
assert( n >= 1 );
return breakInteger(n);
}
};
复制代码
实现2
它包含重叠子问题，下面是记忆化搜索版本：
class Solution {
private:
vector<int> memo;
int max3( int a , int b , int c ){
return max( a , max(b,c) );
}
// 将n进行分割(至少分割两部分), 可以获得的最大乘积
int breakInteger( int n ){
if( n == 1 )
return 1;
if( memo[n] != -1 )
return memo[n];
int res = -1;
for( int i = 1 ; i <= n-1 ; i ++ )
res = max3( res , i*(n-i) , i * breakInteger(n-i) );
memo[n] = res;
return res;
}
public:
int integerBreak(int n) {
assert( n >= 1 );
memo = vector<int>(n+1, -1);
return breakInteger(n);
}
};
复制代码
实现3 动态规划
下面我们使用自底向上的方法，也就是动态规划解决这个问题
class Solution {
private:
int max3( int a , int b , int c ){
return max(max(a,b),c);
}
public:
int integerBreak(int n) {
// memo[i] 表示将数字i分割(至少分割成两部分)后得到的最大乘积
vector<int> memo(n+1, -1);
memo[1] = 1;
for ( int i = 2; i <= n; i++ ) {
// 求解memo[i]
for ( int j = 1; j <= i-1; j++ ) {
// j + (i-j)
memo[i] = max3( memo[i], j*(i-j), j*memo[i-j] );
}
}
return memo[n];
}
};
复制代码
相似问题
- leetcode 279
- leetcode 91
- leetcode 62
- leetcode 63
状态的定义和状态转移
leetcode 198. 打家劫舍
状态的定义
考虑偷取[x...n-1]范围里的房子（函数定义）
状态的转移
f(0) = max{ v(0) + f(2), v(1) + f(3), v(2) + f(4), … , v(n-3) + f(n-1), v(n-2), v(n-1)}(状态转移方程)
解题思路
首先依然是如果没有思路的话，先考虑暴力解法。检查所有的房子，对每个组合，检查是否有相邻的房子，如果没有，记录其价值，找最大值。O((2^n)*n)
注意其中对状态的定义：
考虑偷取[x…n-1]范围里的房子(函数的定义)
根据对状态的定义，决定状态的转移：
f(0) = max{ v(0) + f(2), v(1) + f(3), v(2) + f(4), … , v(n-3) + f(n-1), v(n-2), v(n-1)}(状态转移方程)
实际上我们的递归函数就是在实现状态转移。
198. House Robber
实现代码
class Solution {
private:
// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
vector<int> memo;
// 考虑抢劫nums[index...nums.size())这个范围的所有房子
int tryRob( vector<int> &nums, int index){
if( index >= nums.size() )
return 0;
if( memo[index] != -1 )
return memo[index];
int res = 0;
for( int i = index ; i < nums.size() ; i ++ )
res = max(res, nums[i] + tryRob(nums, i+2));
memo[index] = res;
return res;
}
public:
int rob(vector<int>& nums) {
memo = vector<int>(nums.size(), -1);
return tryRob(nums, 0);
}
};
复制代码
动态规划解法
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if( n == 0 ) {
return 0;
}
// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
vector<int> memo(n, 0);
memo[n-1] = nums[n-1];
for( int i = n-2 ; i >= 0 ; i -- ) {
for (int j = i; j < n; j++) {
memo[i] = max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0) );
}
}
return memo[0];
}
};
复制代码
状态的另一种定义
我们所强调的是对于动态规划来说，我们要清晰自己对状态的定义，在我们之前的定义我们是去考虑偷取[x…n-1]范围里的房子(函数的定义)。对于同样的问题，很多时候我们可以设立不同的状态得到同样正确的答案。
改变对状态的定义：
考虑偷取[0…x]范围里的房子(函数的定义)。实现如下：
记忆化搜索代码实现
class Solution {
private:
vector<int> memo;
//考虑偷取[0..x]范围里的房子
int tryRob(vector<int>&nums, int index){
if (index < 0){
return 0;
}
if (memo[index] != -1){
return memo[index];
}
int res = 0;
for( int i = index; i >= 0; i--){
res = max(res, nums[i] + tryRob(nums, i - 2));
}
memo[index] = res;
return res;
}
public:
int rob(vector<int>& nums) {
int n = nums.size();
memo = vector<int>(n + 1, -1);
if (n == 0){
return 0;
}
return tryRob(nums, n-1);
}
};
复制代码
动态规划代码实现
class Solution {
public:
//考虑偷取[0..x]范围里的房子
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> memo(n, -1);
if (n == 0){
return 0;
}
memo[0] = nums[0];
for(int i = 1; i < n; i++){
for(int j = i; j >= 0; j --){
memo[i] = max(memo[i], nums[j] + (j-2 >= 0? memo[j-2]: 0));
}
}
return memo[n-1];
}
};
复制代码
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Perl语言入门
[美] Randal L.Schwartz、Tom Phoenix / 李晓峰 / 中国电力出版社 / 2002-8 / 48.00元
本书第一版于1993年问世，并从此成为畅销书。本书由Perl社区最著名、最活跃的两位成员写成，是Perl程序设计语言的精髓指南。 Perl最初只是Unix系统管理员的一个工具，在工作日里被用在无数的小任务中。从那以后，它逐步发展成为一种全功能的程序设计语言，特别是在各种计算平台上，它被用作Web编程、数据库处理、XML处理以及系统管理——它能够完成所有这些工作，同时仍然是处理小的日常工作的完......一起来看看 《Perl语言入门》 这本书的介绍吧!
