动态规划(DP)

由纯递归到记忆化搜索再到动态规划

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。(-leetcode 53)

纯递归

int max;
int maxSubWithLastNum(int *nums,int index)
{
    if(index==0) return nums[0];
    int i=maxSubWithLastNum(nums,index-1);
    return i<0?nums[index]:nums[index]+i;
}
int maxSubArray(int* nums, int numsSize){
    max=-1001;
    for (int s=numsSize-1;s>=0;s--)
    {
        max=fmax(max,maxSubWithLastNum(nums,s));
    }
    return max;
}

递归+记忆化

从递归程序中发现

int i=maxSubWithLastNum(nums,index-1);

这一句是重复执行的,每一次循环中都会对某一相同的值进行重复计算,导致浪费了很多时间,所以需要对递归程序的执行过程进行记忆化,此处为建立一个数组将对应位置的maxSubWithLastNum()返回值存储下来

int max;
int maxSubWithLastNum(int *nums,int index,int *mum)
{
    int i;
    if(index==0) return nums[0];
    if(mum[index-1]==-10001)
    {
        i=maxSubWithLastNum(nums,index-1,mum);
        mum[index-1]=i;
    }
    else
        i=mum[index-1];
    return i<0?nums[index]:nums[index]+i;
}
int maxSubArray(int* nums, int numsSize){
    max=-10001;
    int mum[numsSize];
    for(int w=0;w<numsSize;w++) mum[w]=-10001;
    for (int s=numsSize-1;s>=0;s--)
    {
        max=fmax(max,maxSubWithLastNum(nums,s,mum));
    }
    return max;
}

纯dp

根据记忆化后的递归程序,写出对应的状态转移方程,如果把记忆化理解成将递归程序的过程产生的值放到数组中存储起来的话.那么动态规划就是将记忆化这个过程倒过来递推一遍(由递归到递推),记忆化与dp的区别除了在于顺序的不同以外,还区别于记忆化是用函数递归实现的,而动态规划是用数组递推实现的

int maxSubArray(int* nums, int numsSize){
    int max=nums[0];
    int mum[numsSize];
    for(int w=0;w<numsSize;w++) mum[w]=-10001;
    mum[0]=nums[0];
    if(numsSize==1) return nums[0];
    else{
        for (int s=1;s<numsSize;s++)
        {
            mum[s]=mum[s-1]<0?nums[s]:mum[s-1]+nums[s];
            max=fmax(max,mum[s]);
        }
    }
    return max;
}

状态

在使用动态规划解题时,我们往往将和子问题相关的某个变量的一组取值,成为一个状态,一个状态对应一个或多个子问题,所谓某个状态下的值,就是这个状态所对应的子问题的解

状态空间

所有状态的集合,构成问题的状态空间

状态转移方程

找出不同状态之间如何迁移,即如何从一个或多个已知的状态,求出另一个状态的值(递推型)

特点

• 问题具有最优子结构性质,如果问题的最优解所包含的子问题的解也是最优的
• 当前的某个状态值一旦确定,则此后需要用到该状态值时与取得该状态值的过程无关