leetcode题解(动态规划)

动态规划本质依然是递归算法，只不过是满足特定条件的递归算法；动态规划是一个设计感比较强，艺术感比较强的一种算法设计思想。
什么是动态规划 定义
将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。
我们先解决小数据量的问题，之后层层递推来解决更大数据量的问题，通常这个过程就叫做动态规划。这个时间和记忆化搜索的时间复杂度是相当的，不过动态规划没有递归的调用，不需要额外调用和栈空间。
动态规划是一个设计感比较强，艺术感比较强的一种算法设计思想。
一个简单例子
```c++
#include 
#include 

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("<
#### 分析

>通过计时我们会发现这个算法很慢，为什么这个解法效率这么低呢？当我们需要计算fib(5)时，它的递归树是：

[![](http://oseihavwm.bkt.clouddn.com/Fibonacci.png)](http://oseihavwm.bkt.clouddn.com/Fibonacci.png)

>从这个图可以看出这里面有大量的重复计算，我们怎样避免呢，我们可以在程序的外面做一个数组memo，其实memo[i]就记忆了第i个斐波那契数列。

#include 
#include 
#include 
using namespace std;

vector 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(n+1,-1);

    time_t startTime = clock();
    int res = fib(n);
    time_t endTime = clock();

    cout<<"fib("<
>我们采用一个memo数组来记忆，所以叫做记忆化搜索。记忆化搜索其实就是在递归的过程中添加计划化，是一种自上向下的解决问题，我们假设基本的问题已经解决了，我们已经会求fib(n-1)和fib(n-2)了，那么我们就能求第n个数了。

>如果我们能自上而下解决问题，我们也能自下而上解决问题，只不过很多时候我们习惯于前者。

```c++

    #include 
    #include 
    #include 
    using namespace std;

    // 动态规划
    int fib( int n ){

 vector 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("<
第一个动态规划问题
leetcode 70. 爬楼梯

解题思路

我们来看一下递归的思路，把一个大的问题分解成小的问题。


代码实现（递归）
#include 
    #include 

    using namespace std;

    // 记忆化搜索
    class Solution {
    private:
 vector 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(n+1,-1);
     return calcWays(n);
 }
    };
代码实现（动态规划）

我们会发现和上面斐波那契一样，很轻易可以转化为动态规划解法。

#include 
    #include 

    using namespace std;

    // 动态规划
    class Solution {

    public:
 int climbStairs(int n) {

     vector 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 
    #include 

    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 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(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 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 memo;

 // 考虑抢劫nums[index...nums.size())这个范围的所有房子
 int tryRob( vector &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& nums) {

     memo = vector(nums.size(), -1);
     return tryRob(nums, 0);
 }
    };

动态规划解法
    class Solution {

    public:
 int rob(vector& nums) {

     int n = nums.size();

     if( n == 0 ) {
  return 0;
     }

     // memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
     vector 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 memo;
    //考虑偷取[0..x]范围里的房子
    int tryRob(vector&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& nums) {
 int n = nums.size();
 memo = vector(n + 1, -1);
 if (n == 0){
     return 0;
 }

 return tryRob(nums, n-1);
    }
};

动态规划代码实现
class Solution {

public:

    //考虑偷取[0..x]范围里的房子
    int rob(vector& nums) {
 int n = nums.size();
 vector 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];

    }
};
相似问题
leetcode 213
leetcode 337
leetcode 309
原创始发于慕课网
leetcode题解(动态规划)

C/C++/C#相关栏目本月热门文章
