当前位置:   article > 正文

C++---算法学习笔记之动态规划(一)入门_动归算法

动归算法

一. 关于动归的一些概念

不要小瞧概念,有时候 一些概念性的术语可以帮助你更深入的了解一门算法,在这里把一些我认为重要的概念交代清楚。

1.1 什么是动归?

动归是是分治思想的延伸,通俗一点来说就是大事化小,小事化无的艺术。
在将大问题化解为小问题的分治过程中,保存对这些小问题已经处理好的结果,并供后面处理更大规模的问题时直接
使用这些结果。

1.2 动归的特征
  • 原来的问题可以分解成几个相似的子问题
  • 所有的子问题都只需要解决一次
  • 存储子问题的解
1.3动归的四个本质(重要)
  • 状态定义
  • 状态间的转移方程
  • 状态的初始化
  • 返回结果

所有用动归解题的过程中,只要将上述4个要素定义清楚,那么就算成功了。

1.4 运用动归解决的题目场景(动归解题信号)
  • 最大值、最小值问题
  • 可行或不可行的方案问题
  • 求方案个数问题
  • 题目中包含“是否可以用”等规划性问题

二. 通过实战感受动归思想

概念说再多都只是纸上谈兵,下面将由易到难,通过三道比较经典,难度比较低的动归算法题来感受动态规划的思维,作为动归入门学习。

2.1 斐波那契数列

上机练习地址:牛客–斐波那契数列

题目描述:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。 n<=39

这个题目已经写烂了,递归的方法就不再赘述,来看看这题目在动归的思维下是什么样子。
上面已经提到,所有用动归解的题,核心就是找四个量:状态定义、状态转移方程、状态初始化、返回值。那么在这个题目中,这四个量非常明显可以找出。

状态定义:斐波那契数列的第i项的值
状态方程:F(i)=F(i-1)+F(i-2)
状态初始化:F(0)=0,F(1)=1
返回值:F(n)

源代码

class Solution {
public:
    int Fibonacci(int n) {
    
        int* F=new int[n+1];//用来保存每一次结果的值
        
        //初始化
        F[0]=0;
        F[1]=1;
        for(int i=2;i<=n;i++)
        {
            //转换方程
            F[i]=F[i-1]+F[i-2];
        }
        //返回值
        return F[n];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

上述方法开辟了一个数组用于保存每次结果的值,实际上,可以只通过一个变量保存最终的值,节省更多的空间。代码如下:

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=0)
        {
            return 0;
        }
        if(n==1||n==2)
        {
            return 1;
        }
        //初始化
        int first=1,second=1;
        int fn=0;
        for(int i=3;i<=n;i++)
        {
            //状态转移方程
            fn=first+second;
            first=second;
            second=fn;
        }
        return fn;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
2.2 青蛙跳台阶

上机练习地址:牛客—变态青蛙跳台阶

题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这个题目应该也都见得多,递归解法也不再谈。但是这个题目和上一个斐波那契数列比,状态转移方程没有那么容易get到,下面我通过画图来描述。
在这里插入图片描述
通过写出前面几阶台阶的方法数,我们可以递推出,当前第i阶台阶方法数等于前一阶(也就是第i-1阶)台阶方法数的两倍,由此得到转移方程为F(i)=2*F(i-1),写出四要素。

状态定义:跳上第i级台阶的方法数
状态转移方程:F(i)=2*F(i-1)
状态初始化:F(1)=1
返回值:F(n)

代码:

class Solution {
public:
    int jumpFloorII(int number) {
        if(number<=0)
        {
            return 0;
        }
        //初始化
        int f1=1;
        //状态定义
        int fn=f1;
        for(int i=2;i<=number;i++)
        {
            //转换方程
            fn=fn*2;
        }
        //返回值
        return fn;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

补充拓展
该题目如果改编一下:现在让它变成一个正常的青蛙,限制它 一次只能跳1阶或者2阶,现在该如何解答
变化的只有转移方程,由于青蛙一次只可以跳1阶或者2阶,所以任意第i个台阶的方法数都=前一个(第i-1个)台阶的方法数+前两个(第i-2)个台阶的方法数,因为第i个台阶只能由第i-1个台阶和第i-2个台阶跳过来。

定义状态:f(i)跳上第i级台阶的方法数
状态转移方程:f(n)=f(i-1)+f(i-2)
设定状态初始值:f(0)=1;f(1)=1;f(2)=2
返回值:f(n)

代码:

class Solution {
public:
    int numWays(int n) {
        if(n==0||n==1)
        {
            return 1;
        }
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=2;i<=n;i++)
        {
            dp[i]=(dp[i-1]+dp[i-2])%(int)(1e9+7);//力扣要求,结果要取模 1e9+7(1000000007)
        }
        return (dp[n])%(int)(1e9+7);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
2.3 最大连续子数组和

上机练习地址:牛客—连续子数组的最大和

题目描述
在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和。

同样通过画图来递推状态方程,红框内的为当前最大连续子数组。
在这里插入图片描述
这里的F(i)是在:前一个以i-1元素结尾的连续最大子数组和+array[i] 与 array[i]之间找最大值。 也就是说,比如F(2),只会在(6,-3,-2)和(-3)之间选择最大值,为什么抛弃(-3,-2)?因为(6,-3)是以第i-1个元素结尾的最大连续子数组和。类似的,F(3)选择时会抛弃(-3,-2,7),(-2,7)。

状态定义:
F(i) 以第i+1个元素结尾的最大连续和
状态方程:
F(i)=max(F(i)+arr[i],arr[i])
初始化:
F(0)=arr[0]
返回值:
max(F(i)) i<n

代码
1.开辟数组保存每次当前元素结尾的最大连续和F(i)

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        
        vector<int> F(array.size());//用于保存每次以当前元素结尾的最大连续和F(i)
        //初始化
        F[0]=array[0];
        
        for(int i=1;i<F.size();i++)
        {
            //转移方程
            F[i]=max(F[i-1]+array[i],array[i]);
        }
        
        int maxsum=F[0];//用于保存F(i)的最大值
        //找最大的和
        for(int i=1;i<F.size();i++)
        {
            maxsum=max(maxsum,F[i]);
        }
        //返回值
        return maxsum;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

2.不开辟数组,每次更新最大连续子数组和

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        //初始化
        int cursum=array[0];//代表当前的连续子数组和
        int maxsum=array[0];//最大连续子数组和
        for(int i=1;i<array.size();i++)
        {
            //转移方程
            cursum=max(cursum+array[i],array[i]);
            //更新每次最大的子数组和
            maxsum=max(maxsum,cursum);
        }
        //返回值
        return maxsum;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

两种方法都可以。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/691550
推荐阅读
相关标签
  

闽ICP备14008679号