将数组nums拆分成k个连续子数组的一种递归公式写法

shaowu459

现在有一个数组nums，需要将nums拆分成k个连续子数组，返回拆分的方案中每组的和值的最大值中的最小值。

例如，数组nums=[7,2,5,10,8]，k=2，拆分成两个连续子数组有以下几种方案：


各种拆分方案中的最大值列示在最右侧，其中的最小值为18，即为所求。

题目数据源如下：

shaowu459

提供一种递归公式写法，其中递归部分公式完全引用LAMBDA函数递归：m选n所有组合问题帖子中9楼的方法。


以[7,2,5,10,8]这个数组为nums，k=3为例分析下公式思路。将数组想象成一块板子，上面每个小方块中包含一个数字，分割成3个连续的子数组，也就是在板子上切两刀，板子就分成了三块，每块是一个连续的子数组。


例如从第一个数字和第二个数字之间切一刀，第二个和第三个数字之间切一刀：

通过上面的分析可知，将nums拆分为k个连续子数组需要切k-1刀，也就是我们只需要找到所有切分的位置就可以了。我们可以把所有的切分位置先编号：

切分位置一共4个，编号从左到右分别是1、2、3、4，也就是原字符串中逗号的编号，可以把每个逗号看成拆分点。下面就简单了，我们只需要从所有逗号中挑选出切第几个逗号即可，也即从{1,2,3,4}这个数组中任意挑出2个的所有可能的组合。也就是在m选n里m=4，n=2。


定义的名称gx和另外帖子里的一样：

1. =LAMBDA(m,n,IF(n=1,m,IF(ROWS(m)=n,TOROW(m),VSTACK(IFNA(HSTACK(@m,gx(DROP(m,1),n-1)),@m),gx(DROP(m,1),n)))))

复制代码

另m=4，n=2，返回结果如下：


每一行的数字代表着第若干个逗号的编号，是几就代表着从第几个逗号的位置切一刀。例如第一行的{1,2}，切分出来的结果就是{7},{2},{5,10,8}这三个数组。

shaowu459

知道了切分位置，一种处理方式是可以把原字符串对应位置的逗号改成其他符号，例如“@”，然后再按“@”拆分即可。


针对拆分出来的3个字符串，"7"，"2"，"5,10,8"，再分别按照逗号拆分，然后求和，得到这一组的3个值：7、2、23，然后求得最大值23。

针对每一种切分方案都得到最大值后，再取最小值即可。

shaowu459

工作表单元格中输入的公式如下：

1. =MIN(BYROW(gx(SEQUENCE(ROWS(TEXTSPLIT(A2,,","))-1),B2-1),LAMBDA(x,MAX(BYROW(--TEXTSPLIT(REDUCE(A2,SORTBY(x,-x),LAMBDA(m,n,SUBSTITUTE(m,",","|",n))),",","|",,,0),LAMBDA(y,SUM(y)))))))

复制代码

shaowu459

公式简要说明如下：

=MIN(       取每组结果中的最小值
    BYROW(
        gx(SEQUENCE(ROWS(TEXTSPLIT(A2, , ",")) - 1), B2 - 1),  使用m选n递归公式获得所有切分方案的逗号编号
        LAMBDA(x,
            MAX(      求每个拆分方案中的每组结果最大值
                BYROW(       对每组拆分的结果求和
                    --TEXTSPLIT(         按|将字符串拆分为k-1组
                        REDUCE(
                            A2,
                            SORTBY(x, -x),    从最大编号的位置开始将逗号替换为其他字符，公式中使用的是|
                            LAMBDA(m, n, SUBSTITUTE(m, ",", "|", n))
                        ),
                        ",",
                        "|",
                        ,
                        ,
                        0
                    ),
                    LAMBDA(y, SUM(y))   对每个方案中的每组拆分结果求和
                )
            )
        )
    )
)

剑指E

只能支持最多10个数字，最多分6组

1. =LET(a,(LEN(A2)-1)/2,b,B2-1,MIN(REDUCE("",TOCOL(IF(SEARCH(TEXT(SEQUENCE(10^b)-1,REPT("!*0",b)),CONCAT(SEQUENCE(a))),SEQUENCE(10^b)-1),3),LAMBDA(x,y,VSTACK(x,MAX(MAP(TEXTSPLIT(REDUCE(A2,SORT(--MID(y,SEQUENCE(b),1),,-1),LAMBDA(m,n,SUBSTITUTE(m,",",";",n))),";"),LAMBDA(u,SUM(--TEXTSPLIT(u,","))))))))))

复制代码

alan57

1. =LET(b,REDUCE("",SEQUENCE(ROWS(TEXTSPLIT(A2,,","))),LAMBDA(x,y,VSTACK(x,x&y))),MIN(BYROW(DROP(REDUCE(0,FILTER(b,LEN(b)=B2-1),LAMBDA(x,y,VSTACK(x,TOROW(MID(y,ROW(INDIRECT("1:"&B2-1)),1))))),1),LAMBDA(s,MAX(BYROW(--TEXTSPLIT(REDUCE(A2,SORTBY(s,-s),LAMBDA(x,y,SUBSTITUTE(x,",","/",y))),",","/",,,0),SUM))))))

复制代码

学超人一招。用全子集倒插入。

zpy2

shaowu459 发表于 2024-1-12 13:47
提供一种递归公式写法，其中递归部分公式完全引用LAMBDA函数递归：m选n所有组合问题帖子中9楼的方法。


...

感谢分享解题思路。
参与一下。
=webservice("https://e.anyoupin.cn/eh3/?getMinSum~7,2,5,10,8~2")