【算法-动态规划】、子序列累加和必须被7整除的最大累加和

【算法-动态规划】、子序列累加和必须被7整除的最大累加和

一、dp

1.1 题目理解

一个数组 nums, 有很多子序列, (子序列 不要求 连续),
其中, 累加和 可被 7 整除的 那些子序列中,
返回 最大累加和

本题没有在线测试链接, 需要对数器验证

1.2 思路

除7后的余数, 可维护
维护 dp[i][j], 其表示 nums[0…i-1] 范围内(左比右闭区间) 的子序列, 累加和 除7后余数为 j 的, 最大累加和
i 从前向后遍历, 结合 dp[i][j] 和 nums[j] % 7, 得出 dp[i+1][j]
最终返回 dp[n][0] 即可, 其表示 nums[0…n-1] 范围内(左比右闭区间) 的子序列.

1.3 初始值

当 i = 0 时, 即 nums[0…-1] 范围的子序列, 实际为空集. 所以 无论 j = 0/1/2/3/4/5/6 对应的 dp[i][j] 都是 0.

1.4 递推公式

如何得到 dp[i][j] 呢? 有如下两种情况:

1. 若 不保留 nums[i-1], 则 dp[i][j] = dp[i-1][j]. 即 nums[0…i-1]的子序列余j的最大累加和 == nums[0…i-2]的子序列余j的最大累加和
2. 若 保留 nums[i-1], 假设 nums[i-1] % 7 得到 x, 则分为如下两种情况:
   2.1 若 x < j, 则 dp[i][j] = dp[i-1][j-x], 例如 j 为 4, 而 x 为 1, 则只需要 dp[i-1][3] 即可(其中 4-1=3, 即只需凑够 余数为 3 即可)
   2.2 若 x >= j, 则 dp[i][j] = dp[i-1][7+j-x], 例如 j 为 4, 而 x 为 13(即%7余6), 则只需要 dp[i-1][5] 即可(其中 7+4-6=5, 即只需凑够余数为 5 即可)

因此可总结递推公式如下:
dp[i][j] = max(dp[i-1][j], dp[i-1][ (7+j-x)%7 ] + nums[i-1])

1.5 返回值

最终返回 dp[n][0] 即可, 即在 nums[0…n-1] 范围内, 除7余数为 0 的值

1.6 代码

// go
package main

import (
        "math/rand"
        "log/slog"
)

// 对数器
func main() {
        n, v := 15, 30
        times := 20000
        slog.Info("测试开始")
        for range times {
                nums := randArr(n, v)
                a1 := f1(nums)
                a2 := f2(nums)
                if a1 != a2 {
                        slog.Error("不匹配", a1, a2)
                }
        }
        slog.Info("全部匹配")
}

// dp 法
func f2(nums []int) int {
        n := len(nums)
        // dp[i][j] 表示在 nums[0...i-1] 范围内, 各子序列中, 累加和 除7余数为 j 的最大累加和.
        // dp[i][j] = -1 则表示不存在
        dp := make([][7]int, n+1) // 注意, 下标从0到n左比右闭区间, 共n+1个元素
        dp[0][0] = 0
        for j := 1; j < 7; j++ {
                dp[0][j] = -1
        }
        for i := 1; i <= n; i++ {
                for j := range 7 {
                        dp[i][j]=dp[i-1][j] // 不留 nums[i-1] 的情况

                        // 留 nums[i-1] 的情况
                        x := nums[i-1] % 7 // x 是当前 nums[i-1] 的余数
                        if need := dp[i-1][(7+j-x)%7]; need != -1 { // !=-1 表示存在这样的子序列
                                dp[i][j] = max(dp[i][j], need + nums[i-1]) // 情况1: x <= j; 情况2: x > j
                        }
                }
        }
        return dp[n][0]
}

// 暴力法
func f1(nums []int) int {
        var dfs func(i, s int) int // nums[0...i-1]已有子序列和为s的情况下, 求遍历到nums[i] 时的子序列和
        dfs = func(i, s int) int {
                if i == len(nums) {
                        if s % 7 == 0 {
                                return s // 可被7整除, 则返回此 子序列和
                        }
                        return 0 // 返回0, 表示 无子序列和 满足 可被7整除
                }
                return max( dfs(i+1, s), dfs(i+1, s+nums[i]) )
        }
        return dfs(0, 0)
}

func randArr(n, v int) []int {
        arr := make([]int, n)
        for i := range arr {
                arr[i] = rand.Intn(v)
        }
        return arr
}              

代码

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts