【LeetCode】09动态规划Part03

【LeetCode】09动态规划Part03 343. 整数拆分、96. 不同的二叉搜索树

343. 整数拆分

题目链接：https://leetcode.cn/problems/integer-break/description/

思路

思路一：贪心算法

根据自己的不断地测试发现，如果一个数n(n>3)，不断地拆出来3，拆到最后会出现3种情况：

1. n % 3 == 0：最大的乘积数为pow(3, n / 3)
2. n % 3 == 2：意味着拆到最后一个数为2，那么最大的乘积数是pow(3, n / 3) * 2
3. n % 3 == 1：意味着拆到最后一个数为1，那么少拆一个3，使其最后乘以4，最大乘积数为pow(3, n / 3 - 1) * 4

确实也AC了这道题目，核心思想就是贪更多的3。至于为什么并不是很理解，也没有证明

思路二：动态规划