leetcode 343 整数拆分

1.这个题拿到之后没有什么思路，此时就应该考虑暴力法。然而每次不知道要拆成几份，没办法用循环，所以想到用递归。

如图所示进行递归，显然有很多重复的计算，所以用自底向上的动态规划。

2.还有一个问题就是memo[i]是如果拆开i的话的最大值，有些数字比如5=2+3,2*3=6>5,这种数字memo[i]>i,拆开更好，但有的数拆开要比原来的数小，所以要进行判断，选择最大的数字。还要注意一点是至少要拆成两个数字。

#include <bits/stdc++.h>

using namespace std;

class Solution {

public:

    int integerBreak(int n) {

        vector<int>memo(n+, );

        memo[] = ;

        memo[]=;

        int i, j;

        int max;

        for (i = ; i <= n; i++)

        {

            max=;

            for (j = ; j <=(i-); j++)

            {

                if((memo[j]>(j)?memo[j]:j)*(memo[i-j]>(i-j)?memo[i-j]:i-j)>max)

                    max=(memo[j]>(j)?memo[j]:j)*(memo[i-j]>(i-j)?memo[i-j]:i-j);

            }

            memo[i]=max;

        }

        return memo[n];

    }

};