整数n拆成俩数

j的取值从1-n或者是1--n/2

使得n=j*(n-j)俩数比较

而在前j数中已经求出拆分后的最大值也就是dp[i-j]，打个比方说dp[3]=2，隐含了拆分成1+2俩和数相乘为最优值，但是这里有特殊情况，4的两和数相乘比2*dp[2]要大，所以要比较，比较完了后和dp[i]比较，保留目前为止比较的最大值。

不比较dp[i]，则最大值取j最后一次遍历的比较值

n/2之前的和n/2之后的求和数比较值一致，只改变了位置，可以做一个剪枝

#include <algorithm>
#include <vector>
#include <iostream>
#include<cmath>
using namespace std;int main()
{int n = 3;vector<int>dp(n + 1, 0);if (n == 2)return 1;dp[0] = 0;dp[1] = 1;dp[2] = 1;for (int i = 3;i <= n;i++)for (int j = 1;j <=i;j++){dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));}for (auto m : dp)cout << m<<" ";
}//dfs深度优先搜索写的/*
vector<int> ans;void backtracking(int product, int index,int n) {if (index == 0) {ans.push_back(product);return;}for (int i = 1; i <=index; i++) {if (n - i == 0)continue;product *= i;backtracking(product, index - i,n);product /= i;}
}int main() {int n = 29;int product = 1;backtracking(product, n,n);cout << *max_element(ans.begin(),ans.end());return 0;
}
*/