p94-p98 键指offer——动态规划与贪婪算法+面试题14：剪绳子( 二 ) _算法

分析：
代码：
int maxProductAfterCutting_dp(int length){if(length == 0 || length ==1)return 0;if(length == 2)return 1;if(length == 3)return 2;int *dp = new int[length+1];//最终要求length的最优解dp[0] = 0;dp[1] = 1;dp[2] = 2;dp[3] = 3;int max=0;for(int i=4;i max)max = x;dp[i] = max;}}max = dp[length];//resultsdelete[] length;return max;}
【p94-p98键指offer——动态规划与贪婪算法+面试题14：剪绳子】int maxProductAfterCutting_tanlan(int length){//-----------------0,1,2,3自行解决--------------------if(length == 0 || length ==1)return 0;if(length == 2)return 1;if(length == 3)return 2;//------------------仍然是长度大于等于4时开始有了多种减法------------------//尽可能多减去长度为3的绳子int timesOf3 = length/3;//判断当绳子剩下长度为4时，不能再减去长为3了,因为此时2*2的价值更大，所以3的倍数-1if(timesOf3 % 3 == 1)timesOf3 -= 1;//当剩下的值为0，2或者4时的操作，就是让其减去2int timesOf2 = (length - timesOf3*3)/2;//剩下绳子长度不可能为1，因为4里把1包括了；不可能为3因为3的倍数都会被减去return (int)(pow(3,timesOf3))*(int)(pow(2,timesOf2));//结果就是剪成长度为3或者2，所以有了这个操作}