《剑指offer》：贪心算法

深藏阁楼爱情的钟 2023-02-16 04:20 25阅读 0赞

**一、剪绳子**

**题目描述：**给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k\[0\],k\[1\],...,k\[m\]。请问k\[0\]xk\[1\]x...xk\[m\]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

**解答思路：**目标是求解最优解，整体问题的最优解是依赖各个子问题的最优解，这时可以用动态规划来解决。当绳子长度为2时，只可能简称长度为1的两段，所以f(2)=1；当绳子长度为3的时候，可以剪成长度为1和2的两段，所以f(3)=2；当绳子长度为4的时候，可以剪成长度为1和3，也可以简称2和2的两段，f(4)=4。所以，f(n)=max(f(i))\*f(n-i))。

注意：这里数组中循环的数是每次切割最小的段长，不是解的值

class Solution {
    public:
        int cutRope(int number) {
            if(number<0) return 0;
            if(number<3) return 1;
            if(number==3) return 2;
            int *p=new int[number];
            p[0]=0; //这里只赋值最小的段长
            p[1]=1;
            p[2]=2;
            p[3]=3;
            int max_multi;
            for(int i=4;i<=number;i++)
            {
                max_multi=0;
                for(int j=1;j<=i/2;j++)
                {
                    int temp=p[j]*p[i-j];
                    if(temp>max_multi){max_multi=temp;}
                }
                p[i]=max_multi;
            }
            max_multi=p[number];
            delete[] p;
            return max_multi;
        }
    };

**二、变态跳台阶**

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

**解答思路：**先对这个问题进行分解。当有n个台阶的时候，有n种跳法，可以一步跳n个台阶上去。所以，f(n)=f(1)+f(2)+f(3)+...+f(n-1)+1=![2^\{n-1\}][2_n-1]。仍然是斐波那契数列的问题。

class Solution {
    public:
        int jumpFloorII(int number) {
            if(number==0||number==1)
                return number;
            int res=1;
            for(int i=1;i<number;i++)
            {
                res=2*res;
            }
            return res;
        }
    };

[2_n-1]: https://private.codecogs.com/gif.latex?2%5E%7Bn-1%7D