算法之动态规划(剑指offer-剪绳子详解)

动态规划与分治法相似,都是通过组合子问题的解求解原问题.

动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题.其通常用来求解最优化问题.

动态规划求解问题的四个特点:

1)求一个问题的最优解.

2)整体问题的最优解依赖于各个子问题的最优解.

3)我们把大问题分解成若干个子问题,这些小问题之间还有相互重叠的更小的子问题.

4)用从上往下的顺序先计算小问题的最优解,并存储下来,再以此为基础求取大问题的最优解.

通常按照4个步骤设计一个动态规划算法:

1.刻画一个最优解的结构特征.

2.递归地定义最优解的值.

3.计算最优解的值,通常采用自底向上的方法.

4.利用计算出的信息构造出一个最优解.

先分析一个例子:

算法之动态规划(剑指offer-剪绳子详解)

可以将此问题,从底向上动态分解一下.

我们可以观察一下所有最优收益值ri(i=1,2,...,10)及对应的最优切割方案.(每一步都是重新将子问题的最优值相加计算出)

r1=1,切割方案1=1(无切割)

r2=5,切割方案2=2(无切割)

r3=8,切割方案3=3(无切割)

r4=10,切割方案4=2+2

r5=13,切割方案5=2+3

r6=17,切割方案6=6(无切割)

r7=18,切割方案7=1+6或7=2+2+3

r8=22,切割方案8=2+6

r9=25,切割方案9=3+6

r10=30,切割方案10=10(无切割)

如果说上面的例子你认真的过一遍相信对动态规划会有一定的了解了.

剑指offer面试题14剪绳子:

题目:给你一根长度为n的绳子,请把绳子剪成m段,(m,n都是整数,n>1,并且m>1),每段绳子的长度都记为k[0],k[1],...,k[m].请问k[0]*k[1]*...*k[m]的最大乘积是多少?例如,当绳子的长度为8时,我们把它剪成长度为2,3,3,的三段,此时得到的最大乘积是18.

分析:因为n>1,m>1,所以绳子必须要剪,且绳子长度要大于1才可以剪.

根据书上的函数推导f(n)=max(f(i)*f(n-i))

这是从上至下的递归公示,我们通常采用的是自下而上的解法.

当绳子长度为2时,只可能剪成长度为1的两段,因此f(2)=1

当绳子的长度为3时,可能把绳子剪成长度为1,1,1或1,1,因为1*2>1*1*1,所以f(3)=2;

int maxProductAfterCutting_solution(int length)
{
    if(length<2)
        return 0;
    if(length==2)
                return 1;
        if(length==3)
                return 2;
//从长度为4的绳子开始计算最优.
        int* products=new int[length+1];
//如果绳子小于4,不再切割直接计算长度,因为绳子的原始长度大于切割后的乘积
        products[0]=0;
        products[1]=1;
        products[2]=2;
        products[3]=3;
        int max=0;
        for(int i=4;i<=length;++i)
        {
            max=0;
            for(j=1;j<=i/2;++j)//剪绳子
            {
                int product=product[j]*product[i-j];
                if(product>max)
                       max=product;
                product[i]=max;
            }
        }
        max=product[length];
        delete[] products;

        return max;
}

动态规划与朴素递归算法比较:朴素递归算法效率之所以低,是因为它反复求解相同的子问题.因此,动态规划方法仔细安排求解顺序,对每个子问题只求解一次,并将结果保留下来.如果随后再次需要此子问题的解,只需要查找保存的结果,而不必重新计算.因此,动态规划是付出额外的内存空间来节省计算时间,是典型的时空权衡.

算法之动态规划(剑指offer-剪绳子详解)

相关推荐