剪繩子

剪繩子

給你一根長度為n的繩子，將繩子剪成m段（m,n>1）,求剪斷之後的最大乘積。

dp思路：為了求解f(i),需要求解出所有可能的f(j)*f(i-j)，並比較得出最大值。

參考代碼：

root@gt:/home/git/Code# ./a.out i = 4 max = 4i = 5 max = 6i = 6 max = 9i = 7 max = 12i = 8 max = 1818root@gt:/home/git/Code# cat max.c #include <stdio.h>#include <stdlib.h>#include <string.h>int max_dp(int len){ int* arr = (int*)malloc((len + 1)*sizeof(int)); memset(arr,0,(len + 1)*sizeof(int)); int max = 0; if(len < 2) return 0; if(len == 2) return 1; if(len == 3) return 2; arr[0] = 0; arr[1] = 1; arr[2] = 2; arr[3] = 3; for(int i = 4;i <= len;i++) { max = 0; for(int j = 1;j <= i/2;j++) { int product = arr[j] * arr[i - j]; if(product > max){max = product;} arr[i] = max; } printf("i = %d max = %d
",i,max); } max = arr[len]; free(arr); return max;}int main(){ int len = 8; int max = 0; max = max_dp(len); printf("%d
",max); return 0;}

greedy思路：當n>=5時，我們儘可能多的剪長度為3的繩子，當剩下的繩子長度為4時，我們剪成2×2。

參考代碼：

root@gt:/home/git/Code# ./a.out 18root@gt:/home/git/Code# cat max.c #include <stdio.h>int multi(int a,int b){ int pow = 1; for(int i =0;i < b;++i) { pow *= a; } return pow;}int max_greedy(int len){ if(len < 2) return 0; if(len == 2) return 1; if(len == 3) return 2; int time3 = len/3; if(len - time3 * 3 == 1){--time3;} int time2 = (len - time3 * 3)/2; return (int)(multi(3,time3))*(int)(multi(2,time2));}int main(){ int len = 8; int max = 0; max = max_greedy(len); printf("%d
",max); return 0;}

推薦閱讀：