侧边栏壁纸
博主头像
mkdir700博主等级

正在思考人生意义的码农

  • 累计撰写 25 篇文章
  • 累计创建 34 个标签
  • 累计收到 3 条评论

【LC】剑指 Offer 14- I. 剪绳子

mkdir700
2022-03-18 / 0 评论 / 1 点赞 / 366 阅读 / 2,503 字

描述

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(mn都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:
2 <= n <= 58

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


标签

#剑指offer #动态规划 #数学 #完全无头绪

0x01 动态规划

本题可使用[[动态规划]]算法。

吐槽自己

当时在做这道题的时候,属于完全没有思路,所以去看了评论和题解。然后更懵逼了,通过代码去理解题目,这真是一个愚蠢的行为。

蚌埠住了,抓狂,烦躁,无能狂怒。没错,我会为了一道题无能狂怒(😩)

刷题不是上战场杀敌,狂暴buff一无是处!!!刷会儿B站,心情平复好了,再来看看为什么代码要这么写。

这是我在题解下看到的一条评论的代码,对于动态规划的第二步就是想不明白为什么要这样写。这里也算是吃了一个教训,请不要盲目的相信自己能从代码推倒出解题的思路

class Solution {
    public int cuttingRope(int n) {
        /*
        dp五部曲:
        1.状态定义:dp[i]为长度为i的绳子剪成m段最大乘积为dp[i]
        2.状态转移:dp[i]有两种途径可以转移得到
            2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个
            2.2 前面单独成一段,后面剩下的单独成一段,乘积为i*(i-j),乘积个数为2
            两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值
        3.初始化:初始化dp[1]=1即可
        4.遍历顺序:显然为正序遍历
        5.返回坐标:返回dp[n]
        */
        // 定义dp数组
        int[] dp = new int[n + 1];
        // 初始化
        dp[1] = 1;  // 指长度为1的单独乘积为1
        // 遍历[2,n]的每个状态
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= i - 1; j++) {
                // 求出两种转移情况(乘积个数为2和2以上)的最大值
                int tmp = Math.max(dp[j] * (i - j), j * (i - j));
                dp[i] = Math.max(tmp, dp[i]);
            }
        }
        return dp[n];
    }
}

我们一定要有先有思路,最终将思路汇聚成代码的。

困惑点

比较困惑的,也是此解法最核心的部分:

int tmp = Math.max(dp[j] * (i - j), j * (i - j));
dp[i] = Math.max(tmp, dp[i]);

假设只剪1次

f(n) 表示长度为n时,剪成若干段各段长度乘积的最大值。

若干段,多少段,不知道?不妨来点简单的,先固定住剪切的次数—1次,也就是分两段。

假设n=4, m=1,即总长度为4,只做切分1次。

那可以得到如下的切法:

1,3
2,2
3,1

剪一次,对于第一段的可能的长度有1,2,3。

所以可以推导出结论,当长度为n时,剪1次,第一段的长度有n-1种可能。

f(i) 表示长度为i时,剪成两段长度的乘积的最大值,在此处i的长度表示第一段的长度。

那么,这个等式就是自然成立了,f(n) = MAX( f(i) x f(n-i) ) . 在目前这个例子里,就是表示第一段的长度与第二段长度的乘积。

如果还没理解,不妨把上面数字一一罗列出来:

i = 1,n - i = 3, f(n) = 1 * 3 = 3;
i = 2, n - i = 2, f(n) = 2 * 2 = 4;
i = 3, n - i = 1, f(n) = 3 * 1 = 3;

最终的结果最大值就是4。转换成代码如下:

n = 4
dp = [1] * n
for i in range(1, n):
	dp[i] = max(i * (n-i), dp[i-1] * 1)
print(dp[-1])

^00532f

ok,上面的情况是我们固定住了m的值,即只剪1次,分为两段的情况。

细心的小伙伴发现dp[i-1] * 1,为什么乘以1

dp[i-1]表示,因为我们分为两段,所以这个1默认就是最后一段的值。例如,n=4, dp[3] * 1 == 3 * 1n=5,dp[4] * 1 == 4 * 1

剪切若干段

题目的实际情况是若干段,既然不知道若干段,那就暴力去解。

  1. 长度为n,当我得知道 f(i) 的值时,可得表达式 f(n) = f(i) * (n-i)
  2. 之前考虑的一个表达式 f(n) = i * (n - i) ,这就是直接分为两段的情况。
  3. 有一个 f(n) = f(n-1) * 1,可以理解为 f(n-1) 的值。

所以,

f(n) = MAX( f(i) * f(n-i), i * (n - i), f(n -1) )

我们是从小往上计算的,所以需要依次计算出,f(1), f(2), f(3), f(4) ... f(n)

f[1]=1,这个不用多说,从 f(2) 开始遍历:

f = [1] * (n+1)
for i in range(2, n+1):
	pass

i2时,我们计算的是 f(2),可以利用 f(1) 的值 ;
i3时,我们计算的是 f(3),可以利用 f(2) 的值;
...
in时,计算得出最终结果。

f = [1] * (n+1)
for i in range(2, n+1):
	# 计算f[i]的值
	d = [1] * (i + 1)
	for j in range(1, i):
		# 三种情况,取最大值
		f[i] = d[j] = max(f[j] * (i - j), j * (i - j), d[j-1] * 1)
print(f[-1])

内层循环和此处的[[#^00532f]]原理一致。

这个 d 列表,可以再优化,最终代码如下:

代码

class Solution:
    def cuttingRope(self, n: int) -> int:
        f = [1] * (n+1)
        for i in range(2, n+1):
            for j in range(1, i):
                f[i] = max(f[j] * (i - j), j * (i - j), f[i])
        return f[-1]
1

评论区