本题考察的是动态规划与贪心算法,有一个疑问,为何i<4时,products[i]=i。
C++版本
#include <iostream>
#include <vector>
using namespace std;
// 动态规划
int maxProductAfterCutting_solution1(int length)
{
if(length < 2)
return 0;
if(length == 2)
return 1;
if(length == 3)
return 2;
int* products = new int[length + 1];
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
for(int i = 4; i <= length; ++i)
{
max = 0;
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 cutRope(int number){
if(number < 2)
return 0;
if(number == 2)
return 1;
if(number == 3)
return 2;
int numOf3 = number/3;
// 当绳子最后剩下的长度等于4,需要变为2*2
if(number - numOf3*3 == 1)
numOf3--;
int numOf2 = (number - numOf3*3)/2;
return (int)(pow(3,numOf3))*(int)(pow(2,numOf2));
}
int main(){
int a[5] = {1,2,3,4,5};
cout<<&a[2]<<" "<<&a[3]<<endl;
cout<<Fibonacci(6)<<endl;
return 0;
}