当前位置：首页 > article >正文

算法日记31：leetcode341整数拆分（DFS-＞记忆化-＞DP）

article 2025/3/1 10:40:09

一、题目

在这里插入图片描述

二、题解

1、动态规划解题思路：

1、重述问题
2、找到最后一步
3、去掉最后一步，问题变成了什么？
原问题的答案=去掉最后一步的问题+？
4、考虑边界

2、结合题目具体分析：

在这里插入图片描述

假设我们拆出了 $5$ 为第k个数

三、DFS实现

//1、拆分n->k(k>=2)个，使得k个数乘积最大
//2、拆出了第k个数x(x<n)
//3、把n-x拆成k-1个数，使得其乘积最大
//答案=把n-5拆成k-1个数的情况下*x1
//4、遍历完全return 1

1、思路解析：

1）枚举拆分某个数 $x 1$ ，并且往下递归，每次乘上拆分出的数 $x 1$

int dfs(int x)
    {
        if(x==0) return 1;  //表示拆分完全
        //if(x<0) return -1e9;
        int res=0;
        for(int i=1;i<x;i++)   //枚举拆分某个数x1
        {
            if(x-i>=0)  //防止越界
            res=max(res,max(i*(x-i),(dfs(x-i)*i)));
        }
        return res;
    }

2）为什么写成 $res = ma x (res, ma x (i * (x - i), (df s (x - i) * i)))$ 而不是 $res = ma x (res, df s (x - i) * i)$

让我们通过一个具体的例子来解释，为什么 res = max(res, max(i * (x - i), (dfs(x - i) * i))) 必须这样写，而如果改成 res = max(res, dfs(x - i) * i) 会出错。

例子：`n = 8`

我们来分析当 n = 8 时的情况，看看两种写法的区别。

正确的写法：`res = max(res, max(i * (x - i), (dfs(x - i) * i)))`

初始调用：dfs(8)
- 我们要将 8 拆分为两个数 i 和 x - i，并递归拆分后选出最大值。
尝试拆分 i = 1：
- x - i = 8 - 1 = 7
- 计算 i * (x - i)：1 * 7 = 7
- 计算 dfs(x - i) * i：dfs(7) * 1，递归调用 dfs(7)，假设 dfs(7) = 6（假设值）。
- 结果是 dfs(7) * 1 = 6 * 1 = 6。
- max(1 * 7, 6 * 1) = max(7, 6) = 7
所以，res 变成了 7。
尝试拆分 i = 2：
- x - i = 8 - 2 = 6
- 计算 i * (x - i)：2 * 6 = 12
- 计算 dfs(x - i) * i：dfs(6) * 2，递归调用 dfs(6)，假设 dfs(6) = 5。
- 结果是 dfs(6) * 2 = 5 * 2 = 10
- max(2 * 6, 5 * 2) = max(12, 10) = 12
所以，res 变成了 12。
尝试拆分 i = 3：
- x - i = 8 - 3 = 5
- 计算 i * (x - i)：3 * 5 = 15
- 计算 dfs(x - i) * i：dfs(5) * 3，递归调用 dfs(5)，假设 dfs(5) = 4。
- 结果是 dfs(5) * 3 = 4 * 3 = 12
- max(3 * 5, 4 * 3) = max(15, 12) = 15
所以，res 变成了 15。
继续尝试更大的 i 值，最后的最大值是 15。

最终，dfs(8) 返回的最大乘积是 15，通过递归拆分和直接拆分的结合找到了最优解。

错误的写法：`res = max(res, dfs(x - i) * i)`

如果我们将代码改为 res = max(res, dfs(x - i) * i)，会出现问题，因为我们 忽略了直接拆分的乘积，只能通过递归拆分得到的乘积来更新 res。

具体问题示例：

初始调用：dfs(8)
- 我们要将 8 拆分为两个数 i 和 x - i，但是只考虑递归拆分。
尝试拆分 i = 1：
- x - i = 8 - 1 = 7
- 计算 dfs(7) * 1，假设 dfs(7) = 6。
- 结果是 dfs(7) * 1 = 6 * 1 = 6
所以，res 变成了 6。
尝试拆分 i = 2：
- x - i = 8 - 2 = 6
- 计算 dfs(6) * 2，假设 dfs(6) = 5。
- 结果是 dfs(6) * 2 = 5 * 2 = 10
所以，res 变成了 10。
尝试拆分 i = 3：
- x - i = 8 - 3 = 5
- 计算 dfs(5) * 3，假设 dfs(5) = 4。
- 结果是 dfs(5) * 3 = 4 * 3 = 12
所以，res 变成了 12。
继续尝试更大的 i 值，最终得到的最大值是 12。

关键问题

忽略了直接拆分的乘积：res = max(res, dfs(x - i) * i) 只考虑了递归拆分后的结果，而没有考虑当前拆分 i 和剩余部分 x - i 之间的乘积。如果我们直接拆分，像 i * (x - i)，有可能得到比递归拆分更大的乘积。
在这个例子中，当 i = 4 时，i * (x - i) = 4 * 4 = 16 是一个直接拆分的结果，而通过递归得到的 dfs(4) * 4 = 12 明显小于 16。因此，直接拆分出的乘积有时会比递归拆分后的乘积更大。
max(i * (x - i), dfs(x - i) * i) 确保了我们在每一步都考虑了直接拆分的乘积和递归拆分后的乘积，从而得出最大乘积。改成 res = max(res, dfs(x - i) * i) 会遗漏直接拆分的潜在最大值，导致结果错误。

2、代码解析：

//1、拆分n->k个，使得k个数乘机最大
//2、拆出了第k个数x(x<n)
//3、把n-x拆成k-1个数，使得其乘积最大
//答案=把n-5拆成k-1个数的情况下*x1
//4、遍历完全return 1
class Solution 
{
public:
    int dfs(int x)
    {
        if(x==0) return 1;  //表示拆分完全
        //if(x<0) return -1e9;
        int res=0;
        for(int i=1;i<x;i++)   //枚举拆分某个数x1
        {
            if(x-i>=0)  //防止越界
            res=max(res,max(i*(x-i),(dfs(x-i)*i)));
        }
        return res;
    }

    int integerBreak(int n) 
    {
        return dfs(n);
    }
};

四、记忆化搜索

1、思路解析

1）在递归(DFS)中，我们发现会出现大量的重复计算，因此我们可以使用记忆化搜索来减少时间复杂度

2）记忆化搜索的数组变量与DFS中有关边界的变量基本一致

2、代码实现

//1、拆分n->k个，使得k个数乘机最大
//2、拆出了第k个数x(x<n)
//3、把n-x拆成k-1个数，使得其乘积最大
//答案=把n-5拆成k-1个数的情况下*x1
//4、遍历完全return 1
class Solution 
{
public:
    int mem[60];
    int dfs(int x)
    {
        if(x==0) return 1;  //表示拆分完全
        //if(x<0) return -1e9;
        int res=0;
        for(int i=1;i<x;i++)   //枚举拆分某个数x1
        {
            if(x-i>=0)  //防止越界
            res=max(res,max(i*(x-i),(dfs(x-i)*i)));
        }
        mem[x]=res;
        return mem[x];
    }

    int integerBreak(int n) 
    {
        return dfs(n);
    }
};

五、动态规划

//1、拆分n->k个，使得k个数乘机最大
//2、拆出了第k个数x(x<n)
//3、把n-x拆成k-1个数，使得其乘积最大
//答案=把n-5拆成k-1个数的情况下*x1
//4、遍历完全return 1

1、思路解析：

1）在DFS中，我们发现影响边界的条件有

我们选择了某个数 $i$ 作为拆分出的第 $k$ 个数
第 $k - 1$ 个数（因为这个数会受第 $k$ 个数影响）

2）遍历每个数字 $i$ ，从 $1$ 到 $n$ ，计算每个 $i$ 拆分后的最大乘积

3）对于每个 $i$ ，遍历所有可能的拆分点 $j$ ，尝试拆分为 $j$ 和 $i - j$

4）然后选择两种拆分方式（直接拆分与递归拆分）中的最大值，更新 $d p [i]$

int integerBreak(int n) {
    dp[0] = dp[1] = 1;  // 初始化dp数组，dp[i]表示拆分数字i得到的最大乘积
    for (int i = 1; i <= n; i++) {  // 外层循环，i代表当前要计算的数字
        for (int j = 0; j < i; j++) {  // 内层循环，j代表拆分点
            // 计算将i拆分为j和i-j两部分后，得到的最大乘积
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];  // 返回dp[n]，即拆分n得到的最大乘积
}

2、代码实现：

//1、拆分n->k个，使得k个数乘机最大
//2、拆出了第k个数x(x<n)
//3、把n-x拆成k-1个数，使得其乘积最大
//答案=把n-5拆成k-1个数的情况下*x1
//4、遍历完全return 1
class Solution 
{
public:
    int dp[60];
    // int mem[60];
    // int dfs(int x)
    // {
    //     if(x==0) return 1;  //表示拆分完全
    //     //if(x<0) return -1e9;
    //     int res=0;
    //     for(int i=1;i<x;i++)   //枚举拆分某个数x
    //     {
    //         if(x-i>=0)  //防止越界
    //         res=max(res,max(i*(x-i),(dfs(x-i)*i)));
    //     }
    //     mem[x]=res;
    //     return mem[x];
    // }

    int integerBreak(int n) 
    {
        //return dfs(n);
        dp[0]=dp[1]=1;
        //遍历每个数字 i，从 1 到 n，计算每个 i 拆分后的最大乘积
        for(int i = 1; i <= n; i ++)
        {
            //对于每个 i，遍历所有可能的拆分点 j，尝试拆分为 j 和 i - j，
            //然后选择两种拆分方式（直接拆分与递归拆分）中的最大值，更新 dp[i]。
            for(int j = 0; j < i; j ++) 
            {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i-j]));
            }
        }
        return dp[n];
    }
};

3、动态转移方程解析：

问题背景：

我们想将一个整数 n 拆分成多个正整数，使得这些数的乘积最大。通过动态规划的方式实现这个问题。

代码分析：

int integerBreak(int n)
 {
    dp[0] = dp[1] = 1;  // 初始化dp数组，dp[i]表示拆分数字i得到的最大乘积
    for (int i = 1; i <= n; i++) 
    {  
    	// 外层循环，i代表当前要计算的数字
        for (int j = 0; j < i; j++) 
        {  
        	// 内层循环，j代表拆分点
            // 计算将i拆分为j和i-j两部分后，得到的最大乘积
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];  // 返回dp[n]，即拆分n得到的最大乘积
}

详细解释：

初始化部分：
```
dp[0] = dp[1] = 1;
```
- dp[i] 表示将整数 i 拆分后得到的最大乘积。
- 我们初始化 dp[0] 和 dp[1] 都为 1，因为这两者的拆分结果是没有意义的（它们没有拆分的意义）。
外层循环：for (int i = 1; i <= n; i++)：
- 外层循环遍历所有的整数 i，从 1 到 n。
- 对于每个 i，我们都想找出一个最优的拆分方式，来使得拆分后的乘积最大。
内层循环：for (int j = 0; j < i; j++)：
- 对于当前的 i，内层循环遍历所有可能的拆分点 j。
- 这里的 j 表示拆分点，意思是我们将 i 拆分成两个部分：j 和 i - j。
核心计算：
```
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
```
这行代码的作用是更新 dp[i]，即当前数字 i 拆分后的最大乘积。
- j * (i - j)：这个是最直接的拆分方式。假设我们将 i 拆分为 j 和 i - j，然后计算这两个数的乘积。
- j * dp[i - j]：这个是递归拆分的方式。我们将 i 拆成 j 和 i - j，然后再继续递归计算 i - j 的最大乘积。因此，dp[i - j] 就表示 i - j 的最优拆分乘积。
通过 max 函数，我们在这两种拆分方式中选出最大值，更新 dp[i]。

举例说明：

假设 n = 5，我们来看看这段代码是如何工作的：

初始化：
- dp[0] = dp[1] = 1
外层循环开始： (i从 1 到 5)
- i = 2：
  - 内层循环：j = 0，拆分 2 为 0 和 2，计算：
    - dp[2] = max(dp[2], max(0 * (2 - 0), 0 * dp[2 - 0])) = max(0, 0) = 0
  - j = 1，拆分 2 为 1 和 1，计算：
    - dp[2] = max(dp[2], max(1 * (2 - 1), 1 * dp[2 - 1])) = max(0, max(1, 1)) = 1
  - dp[2] = 1
- i = 3：
  - 内层循环：j = 0，拆分 3 为 0 和 3，计算：
    - dp[3] = max(dp[3], max(0 * (3 - 0), 0 * dp[3 - 0])) = max(0, 0) = 0
  - j = 1，拆分 3 为 1 和 2，计算：
    - dp[3] = max(dp[3], max(1 * (3 - 1), 1 * dp[3 - 1])) = max(0, max(2, 2)) = 2
  - j = 2，拆分 3 为 2 和 1，计算：
    - dp[3] = max(dp[3], max(2 * (3 - 2), 2 * dp[3 - 2])) = max(2, 2) = 2
  - dp[3] = 2
- i = 4：
  - 内层循环：j = 0，拆分 4 为 0 和 4，计算：
    - dp[4] = max(dp[4], max(0 * (4 - 0), 0 * dp[4 - 0])) = max(0, 0) = 0
  - j = 1，拆分 4 为 1 和 3，计算：
    - dp[4] = max(dp[4], max(1 * (4 - 1), 1 * dp[4 - 1])) = max(0, max(3, 3)) = 3
  - j = 2，拆分 4 为 2 和 2，计算：
    - dp[4] = max(dp[4], max(2 * (4 - 2), 2 * dp[4 - 2])) = max(3, max(4, 4)) = 4
  - dp[4] = 4
- i = 5：
  - 内层循环：j = 0，拆分 5 为 0 和 5，计算：
    - dp[5] = max(dp[5], max(0 * (5 - 0), 0 * dp[5 - 0])) = max(0, 0) = 0
  - j = 1，拆分 5 为 1 和 4，计算：
    - dp[5] = max(dp[5], max(1 * (5 - 1), 1 * dp[5 - 1])) = max(0, max(4, 4)) = 4
  - j = 2，拆分 5 为 2 和 3，计算：
    - dp[5] = max(dp[5], max(2 * (5 - 2), 2 * dp[5 - 2])) = max(4, max(6, 6)) = 6
  - j = 3，拆分 5 为 3 和 2，计算：
    - dp[5] = max(dp[5], max(3 * (5 - 3), 3 * dp[5 - 3])) = max(6, max(6, 6)) = 6
  - dp[5] = 6