leetcode题解(动态规划)

栏目: 编程工具 · 发布时间: 6年前

内容简介:动态规划本质依然是递归算法,只不过是满足特定条件的递归算法;动态规划是一个设计感比较强,艺术感比较强的一种算法设计思想。将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。通过计时我们会发现这个算法很慢,为什么这个解法效率这么低呢?当我们需要计算fib(5)时,它的递归树是:

动态规划本质依然是递归算法,只不过是满足特定条件的递归算法;动态规划是一个设计感比较强,艺术感比较强的一种算法设计思想。

什么是动态规划

定义

将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。

leetcode题解(动态规划)
  • 我们先解决小数据量的问题,之后层层递推来解决更大数据量的问题,通常这个过程就叫做动态规划。这个时间和记忆化搜索的时间复杂度是相当的,不过动态规划没有递归的调用,不需要额外调用和栈空间。
  • 动态规划是一个设计感比较强,艺术感比较强的一种算法设计思想。

一个简单例子

#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)时,它的递归树是:

leetcode题解(动态规划)

从这个图可以看出这里面有大量的重复计算,我们怎样避免呢,我们可以在程序的外面做一个数组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. 爬楼梯

leetcode题解(动态规划)

解题思路

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

leetcode题解(动态规划)

代码实现(递归)

#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. 整数拆分

leetcode题解(动态规划)

解题思路

leetcode题解(动态规划)

对于一个问题如果没有思路时,我们可以先考虑暴力解法。话句话说,我们使用什么样的方式,才能把正整数n的所有分割枚举出来,我们无法知道有几重循环,通常我们需要使用递归的手段。

暴力解法:回溯遍历将一个数做分割的所有可能性。O(2^n)

之所以递归树存在,是因为它有最优子结构

通过求子问题的最优解,可以获得原问题的最优解。

最优子结构

leetcode题解(动态规划)
  • 通过求子问题的最优解, 可以获得原问题的最优解

代码实现

实现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. 打家劫舍

leetcode题解(动态规划)

状态的定义

考虑偷取[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)}(状态转移方程)

解题思路

leetcode题解(动态规划)

首先依然是如果没有思路的话,先考虑暴力解法。检查所有的房子,对每个组合,检查是否有相邻的房子,如果没有,记录其价值,找最大值。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];
        
    }
};
复制代码

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java Message Service API Tutorial and Reference

Java Message Service API Tutorial and Reference

Hapner, Mark; Burridge, Rich; Sharma, Rahul / 2002-2 / $ 56.49

Java Message Service (JMS) represents a powerful solution for communicating between Java enterprise applications, software components, and legacy systems. In this authoritative tutorial and comprehens......一起来看看 《Java Message Service API Tutorial and Reference》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具