剑指offer----动态&贪婪

1. 剪绳子：长度为的绳子，剪成段，各段长度记为,求各段最大乘积多少？

• dp：即为把长度的绳子剪成若干段()的最大乘积。
• 用子问题定义原问题：，
• 由此可知应自底向上计算，保存小的结果。

#include <iostream>
#include<vector>
#include<algorithm>
#include<exception>
#include<set>
#include<map>
using namespace std;

int maxProductAfterCutting(int length)
{
  if(length<2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
     return 2;
    
    //products[i]代表f[i]
    int *products = new int[length+1] ;
    products[0] = 0; // dumps elems
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;
    int max = 0;
    //遍历长度i
    for(int i=4; i<=length;++i)
    {
        max = 0;
        //切割大小为j,只计算前一半即可;
        for(int j=1; j<=i/2; ++j)
        {   
            //根据上述公式计算：取最大那个
            int product = products[j] * products[i-j];
            if(max < product) max = product;    
        }
        products[i] = max;  

    }
    max = products[length];
    delete[] products;
    return max;
}
int main() {
    cout << maxProductAfterCutting(9) << endl;
}

27

• greedy：

int maxProductAfterCuttingGreedy(int length)
{
  if(length<2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
     return 2;
    
    //尽可能去剪长为3的绳子
    int timesOf3 = length / 3;
    // 当绳子为4例外,剪成2*2
    if (length - timesOf3*3==1)
            timesOf3-=1;
    int timesOf2 = (length - timesOf3 * 3) /2;
    return (int)(pow(3, timesOf3) * (int)(pow(2, timesOf2)));
}