递归-记忆化搜索-动态规划

递归-记忆化搜索-动态规划

下面整理动态规划的相关问题，其动态规划和递归有着密切的联系，递归是自顶向下的过程，而动态规划是自底向上的过程。 所谓的顶指的是：复杂的大问题；所谓的底指的是：简单的子问题。

LeetCode 70 ---爬楼梯

假设你正在爬楼梯。需要 n 步你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 步 + 1 步
2.  2 步

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步

下面依次用三种方法进行实现，可以对比一下，会发现其不同点。

具体代码：

/*
//方法一：采用递归的方式---超时
class Solution {
public:
    int climbStairs(int n) {
        if(n==0)
            return 1;
        if(n==1)
            return 1;
        return climbStairs(n-1)+climbStairs(n-2);       
    }
};


//方法二：这是记忆化搜索的方法，能通过，但是还是自顶向下的方式
class Solution {
private:
    vector<int>memo;
    int climb(int n)
    {
        if(n==0)
            return 1;
        if(n==1)
            return 1;
        if(memo[n]==-1)
            memo[n]=climb(n-1)+climb(n-2);        
        return memo[n];
    }
    
public:
    int climbStairs(int n) {
        memo=vector<int>(n+1,-1);      
        return climb(n)；
    }
};
*/

//方法三：这是动态规划的方法--实现了自底向下的方法（从简单问题向复杂问题进行）
class Solution {
public:
    int climbStairs(int n) {
        vector<int>memo(n+1,-1);
        if(n==0||n==1)
            return 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 343---整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

例如，给定 n = 2，返回1（2 = 1 + 1）；给定 n = 10，返回36（10 = 3 + 3 + 4）。

注意：你可以假设 n 不小于2且不大于58。

下面进行了三种方法的对比，代码如下：

具体代码：

class Solution {
private:
    //方法一：递归的实现----超时未通过
    int BreakLine1(int n)
    {
        if(n==1)   //无法分割，返回1
            return 1;
        
        int res=0;
        for(int i=1;i<=n-1;i++)
        //分割成i和n-i两部分
            res=max(max(res,i*BreakLine1(n-i)),i*(n-i));    
        return res;
    }
    
    //方法二：记忆化搜索的方法--自顶向下
    
    vector<int>memo;
    int BreakLine2(int n)
    {
        memo[1]=1;
        
        if(memo[n]==-1)
        {
            int res=-1;
            for(int i=1;i<=n-1;i++)
            //分割成i和n-i两部分
                res=max(max(res,i*BreakLine2(n-i)),i*(n-i));
            memo[n]=res;
        }              
        return memo[n];
    }
    
    //方法三：动态规划方法--自底向上
    int BreakLine3(int n)
    {
        memo[1]=1;       
        for(int i=2;i<=n;i++)            //注意结束条件！！！能取到n
            for(int j=1;j<=i-1;j++)
               //分成了两部分j和i-j。
                memo[i]=max(memo[i],max(j*memo[i-j],j*(i-j)));
        
        return memo[n];        
    }
public:
    int integerBreak(int n) {
        memo=vector<int>(n+1,-1);
        return BreakLine3(n); 
    }
};

LeetCode 198---打家劫舍

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

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

示例 1:

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

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

下面用三种方法进行实现

代码如下：

class Solution {
private:
    //方法一：递归实现---超时
    int toudao1(vector<int>& nums,int index)
    {
        if(index>=nums.size())
            return 0;
        int res=0;
        for(int i=index;i<nums.size();i++)
            res=max(res,nums[i]+toudao1(nums,i+2));    
        return res;
    }
    
    //方法二：记忆化搜索
    vector<int>memo;
    int toudao2(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]+toudao2(nums,i+2));   
        memo[index]=res;
        return res;
    }
    
    //方法三：动态规划--自底向上求解  ---状态定义：index表示偷盗[index,,,,,nums.size()]的范围，如果状态定义
    //换了下面的程序是需要重新改写的。（时刻注意问题的规模---从小规模问题的解去求取大规模问题的解）
    int toudao3(vector<int>nums,int index)
    {
        int n=nums.size();
        memo[n-1]=nums[n-1];
        
        for(int i=n-2;i>=0;i--)
            //求解memo[i]
            for(int j=i;j<n;j++)
                memo[i]=max(memo[i],nums[j]+(j+2<n?memo[j+2]:0));  //这个条件需要注意，j+2有可能超出范围需要注意一下！！！
        
        return memo[0];
        
    }
    
public:
    //这个偷盗的问题需要注意偷盗顺序。
    int rob(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        
        memo=vector<int>(nums.size(),-1);
        
        return toudao3(nums,0);
        
    }
};