动态规划(Dynamic Programming)

一、Dynamic Programming定义

动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。

在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。

• 动态规划具备了以下三个特点:
• 把原来的问题分解成了几个相似的子问题。
• 所有的子问题都只需要解决一次。
• 储存子问题的解。

动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。

• 动态规划问题一般从以下四个角度考虑:
• 状态定义。
• 状态间的转移方程定义。
• 状态的初始化。
• 返回结果。

状态定义的要求：定义的状态一定要形成递推关系。

一句话概括：三特点四要素两本质。

适用场景：最大值/最小值, 可不可行, 是不是，方案个数。

二、斐波那契数列

斐波那契数列

class Solution {
public:
    int Fibonacci(int n) 
    {
        /*if(n==0||n==1)
        {
            return n;
        }
        else
        {
            return Fibonacci(n-1)+Fibonacci(n-2);
        }*/
        if(n==0||n==1)
        {
            return n;
        }
        int n1=0;
        int n2=1;
        int n3=0;
        while(n>1)
        {
            n3=(n1+n2)%1000000007;
            n1=n2;
            n2=n3;
            n--;
        }
        return n3;
    }
};

三、跳台阶扩展问题

类似pow的求解

class Solution {
public:
    int jumpFloorII(int number) 
    {
        if(number==0||number==1)
        {
            return number;
        }
        else
        {
            int ret=1;
            while(number>1)
            {
                ret=ret*2;
                number--;
            }
            return ret;
        }
    }
};

四、最大连续子数组和

连续子数组最大和

class Solution {
public:
    int FindGreatestSumOfSubArray(vector array) 
    {
        if(array.size()==0)
        {
            return 0;
        }
        
        int sum=array[0];
        
        for(int i=0;i