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

两种方法都可以。