我的解題:
上一道剪繩子的題我用的也是動态規劃,不過是兩個for循環,一個一個算出來的
參考大佬的題解,想要乘積越大3的個數就要越多
class Solution {
public:
int cuttingRope(int n) {
vector<long> dp(1001,0);
dp[1]=1;
dp[2]=1;
dp[3]=2;
dp[4]=4;
dp[5]=6;
dp[6]=9;
for(int i=7;i<=n;i++){
dp[i]=(dp[i-3]*3)%1000000007;
}
return dp[n];
}
};