整数分解链接题目链接：https://leetcode-cn.com/problems/integer-break给定一个正整数n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化.返回您可以获得的最大产品。示例1：输入：2输出：1解释：2=1+1，1×1=1。示例2：输入：10输出：36解释：10=3+3+4，3×3×4=36。解释：你可以假设n不小于2，不大于58。思考看到这道题，你会想把它拆分成两个，或者三个，或者四个……下面我们来看看如何使用dynamic规则来解决它。动态规划规则的五部分分析如下：确定dp数组（dp表）及下标的含义dp[i]：拆分数i，最大可得到的乘积为dp[i].dp[i]的定义就是执行整个问题求解过程。如果你不明白下面是哪一步，那就想想dp[i]到底代表什么吧！确定递归公式，想想dp[i]的最大乘积是怎么得到的呢？其实j可以从1开始遍历，然后有两种方法可以得到dp[i]。一种是直接乘以j*(i-j)。一种是j*dp[i-j]，相当于分裂(i-j)。如果不理解这个拆分，可以回忆一下dp数组的定义。那么有同学问，j为什么不拆分呢？j是从1开始遍历的，而splitj实际上是在遍历j的过程中计算出来的。然后从1开始遍历j，比较(i-j)*j和dp[i-j]*j，取最大的。递归公式：dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j));也可以这样理解，j*(i-j)就是简单地将整数拆分为两个相乘的数，而j*dp[i-j]就是拆分为两个或多个相乘的数。如果定义了dp[i-j]*dp[j]，默认情况下会将一个数字强制拆分为4个或更多部分。所以递归公式：dp[i]=max({dp[i],(i-j)*j,dp[i-j]*j});那为什么取最大值的时候还要比较dp[i]呢？因为在推导递归公式的过程中，每次计算dp[i]，都是取最大的那个。应该很多同学对dp的初始化比较困惑，dp[0]dp[1]应该初始化多少？有的解法会给出dp[0]=1,dp[1]=1的初始化，但是解释的很牵强，主要是这个初始化可以过题。从dp[i]的定义严格来说，dp[0]dp[1]不应该被初始化，也就是无意义的值。拆分0和拆分1的最大乘积是多少？这是无解的。这里我只初始化dp[2]=1，从dp[i]的定义来看，将数2拆分得到的最大乘积为1，这个没有异议！确定遍历顺序确定遍历顺序。我们先来看看递归。公式：dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j));dp[i]取决于dp[i-j]的状态，所以遍历i必须从前向后遍历，先dp[i-j]再dp[i]。在枚举j的时候，是从1开始的，i是从3开始的，所以dp[i-j]就是dp[2]，可以通过我们初始化的值来计算。所以遍历顺序是：for(inti=3;i<=n;i++){for(intj=1;j
