(动态规划基础 整数拆分）leetcode 343

整数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;
}
*/