剪绳子（动态规划，贪心算法）

熟悉我的都知道我喜欢一题多解，但是一道题肯定只有一种最适合最快的方式
但是由于是平时的练习，还是多写一点好，哈哈！

1、最优解问题最先考虑就是动态规划dp

• 解题思路：

  • 1.我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来。用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1

  • 2.我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪

  • 3.剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])

  • 4.第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))最后返回dp[n]即可

    class Solution {
    public:
        int cuttingRope(int n) {/
            vector<int> dp(n+1,0);
            dp[2]=1;//起步
            for(int i=3;i<=n;i++)
            {
                for(int j=2;j<i;j++)//剪掉一段为j长的绳子，剩下i-j这么长,从2开始剪
                {
                    dp[i]=max(dp[i],max(j*dp[i-j],j*(i-j)));//状态转移方程现(现态、次态)
                }
            }
            return dp[n];
        }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

2、贪心算法

• 解题思路：
  • 1.果 n == 2，返回1，如果 n == 3，返回2，两个可以合并成n小于4的时候返回n - 1
  • 2.如果 n == 4，返回4
  • 3.如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段
  • 以上2和3可以合并

    class Solution {
    public:
        int cuttingRope(int n) {
            if(n<4)
                return n-1;
            int res=1;//说白了就是本身
            while(n>4)
            {
                res*=3;n-=3;
            }
            return res*n;
        }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

动态规划和贪心属于高级算法的部分，其题还是比较难，再接再厉吧！嘿嘿