古法编程1：整数拆分

题目来源于力扣343题给定一个正整数n将其拆分为k个正整数的和k 2并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例1输入:n 2输出:1解释:2 1 1, 1 × 1 1思路题目描述比较简单但解题对于我这个初学者来说还是比较难的。对于此题我想到了用动态规划但迟迟找不出状态转移方程故考虑暴力。我枚举了n345的情况发现只有n4时其整数乘积才大于或等于n本身并且其k个整数之间的差距比较小如n10时输出为3*3*436。于是我想到了用一个数组arr记录小等于n时的最大乘积然后将n拆成两个数一个作为本身的数值另一个作为arr中记录的数值然后相乘与arr中记录的比较取最大值arr[i]max(arr[i],j*arr[i-j])。具体代码如下class Solution { public: int integerBreak(int n) { vectorint arr(n1,0); if(n2) return 1; if(n3) return 2; arr[1]1; arr[2]2; arr[3]3; for(int i3;in;i) { for(int j1;j(i1)1;j) { arr[i]max(arr[i],j*arr[i-j]); } } return arr[n]; } };在这里我其实取巧了根据题目意思arr[2],arr[3]应该分别为1和2但如果取12的话我发现后面的拆分如果出现2和3时乘积与期望值相比会小一点应为23不用拆分拆分后反而变小了。至于对i向下取整并加1是因为发现拆分的数最大的不超过(n/2)1枚举不用超过这个值。最终还是通过了就是消耗的内存比较多。以上包括了我的代码的思考过程。本人能力有限才刚开始学习算法对于此题的思考或有漏洞或解释浅显。欢迎大家指正。