Problem P25. [算法课动态规划] 整数拆分

本文介绍: Pro ble m P25. [算法课动态规划] 整数拆分给定一个正整数 n ，将其拆分为 k 个正整数的和（ k &g t;= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积。提示:题目数据保证运算过程不超过 int 所能表示的范围输入输入正整数n输出输出可以获得的最大乘积样例标准输入2标准输出1标准输入10标准输出36。

Pro ble m P25. [算法课动态规划] 整数拆分
 给定一个正整数 n ，将其拆分为 k 个正整数的和（ k &g t;= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积。

提示:

2 <= n <= 58
题目数据保证运算过程不超过 int 所能表示的范围
 输入

输入正整数n

输出

输出可以获得的最大乘积

样例

标准输入
2
标准输出
1
标准输入
10
标准输出
36

解题 思路：

有点类似于阶乘，把2，3，4这三个数组单独来看，5以后的数字用递归
2：输出1；
3：输出2；
4：输出4；
5：3 * f(5-3)=3 * f(2)=3 * 2=6 ，令f(2)=2，当n<=4，f(n)=n；当n&g t;4时，输出3 * f(n-3)；
6：3 * f(6-3)=3 * f(3)=3 * 3=9，令f(3)=3；
7：3 * f(7-3)=3 * f(4)=3 * 4=12，令f(4)=4；
8：3 * f(8-3)=3 * f(5)=3 * 6；
……等等依次往后算

#include <iostream&gt;

using namespace std;
int fac(int n)
{

    if(n <=4 ) return n;
    else return 3*fac(n-3);
}
int main()
{
    int n;
    cin &gt;&gt; n;
    if(n == 2)
    {
        cout << 1;
        return 0;
    }
    else if(n == 3)
    {
        cout << 2;
        return 0;
    }
    else if(n == 4)
    {
        cout << 4;
        return 0;
    }
    else
    {
        cout << fac(n);
    }

//    cout << "Hello world!" << endl;
    return 0;
}