uq_43625241302

用户名：uq_43625241302

访问量：3160

签　名：

等　　级
排　　名	7726
经　　验	1287
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

并查集 + 模拟 = 恶心
浏览：558

贪心 + 优先队列
浏览：871

模拟分类（标题不能太短）
浏览：424

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

动态规划：类似最长递增子序列

　　作者: uq_43625241302　　　　发表时间：2023-04-25 17:18:01 浏览：570　|　评论：1　

原题链接：蓝桥杯2023年第十四届省赛真题-数组分割

# 动态规划

## 解题思路
思考：如果求出了所有以每个数字结尾的且和为偶数的数量，则最终的答案是什么？

$$
res = 1 + \sum_{1}^n 以nums[i]结尾且和为偶数的数量
$$

* 其中1表示空集

思考：那如何求以`nums[i]`结尾且和为偶数的集合数量呢？
* 可以模仿求最长递增子序列的思路：
设`dp[i][0]` 表示以 `nums[i]` 结尾且和为奇数的数量
设`dp[i][1]` 表示以 `nums[i]` 结尾且和为偶数的数量
1. 若当前数`nums[i]`为偶数，则遍历前面所有元素`nums[j]`，则有
 * 偶数加偶数和为偶数，所以 `dp[i][1] += dp[j][1]`
 * 偶数加奇数和为奇数，所以 `dp[i][0] += dp[j][0]`
2. 若当前数`nums[i]`为奇数，则遍历前面所有元素`nums[j]`，则有
 * 奇数加奇数和为偶数，所以 `dp[i][1] += dp[j][0]`
 * 奇数加偶数和为奇数，所以 `dp[i][0] += dp[j][1]`

## 代码实现
```java
import java.util.Scanner;

public class Main {

private static final int MAX_VALUE = 1000000007;

public static void main(String[] args) {
        new Main().go();
    }

public void go() {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        while(k-- != 0) {
            int n = sc.nextInt();
            int[] nums = new int[n];
            for(int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            System.out.println(getRes(nums));
        }
    }

public int getRes(int[] nums) {
        int n = nums.length;
        long sum = 0;
        for(int num : nums) sum += num;
        if(sum % 2 != 0) return 0;
        // dp[i][0] 表示以 nums[i] 结尾且和为奇数的数量
        // dp[i][1] 表示以nums[i]结尾且和为偶数的数量
        long[][] dp = new long[n][2];
        long res = 1;   // 初始化为0，因为后期不计算空集
        for(int i = 0; i < n; i++) {
            if(nums[i] % 2 == 0) {
                // 偶数：则当前元素可以但单独成为一个以nums[i]结尾且和为偶数的集合
                dp[i][1] = 1;
                for(int j = 0; j < i; j++) {
                    dp[i][1] = (dp[i][1] + dp[j][1]) % MAX_VALUE;
                    dp[i][0] = (dp[i][0] + dp[j][0]) % MAX_VALUE;
                }
            } else {
                // 奇数：则当前元素可以但单独成为一个以nums[i]结尾且和为奇数的集合
                dp[i][0] = 1;
                for(int j = 0; j < i; j++) {
                    dp[i][1] = (dp[i][1] + dp[j][0]) % MAX_VALUE;
                    dp[i][0] = (dp[i][0] + dp[j][1]) % MAX_VALUE;
                }
            }
            res = (res + dp[i][1]) % MAX_VALUE;
        }
        return (int) (res % MAX_VALUE);
    }

}
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

CodingMe

牛，大佬请问学习动态规划有什么推荐的视频或者书籍资源吗？动态规划学得好痛苦啊

2024-03-27 19:44:39

uq_43625241302

TA的其他文章

你可能喜欢

明明的随机数（C++代码）

【明明的随机数】（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

【出圈】（C语言代码）用单项循环链表

动态规划：类似最长递增子序列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

C语言训练-排序问题<1> （C语言代码）

Pascal三角（C语言代码）格式错误

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

回文数字（C语言代码）

uq_43625241302

TA的其他文章

你可能喜欢

明明的随机数 （C++代码）

【明明的随机数】 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

【出圈】 （C语言代码）用单项循环链表

动态规划：类似最长递增子序列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-舍罕王的失算 （C++代码）（都给答案了还算什么）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

C语言训练-排序问题<1> （C语言代码）

Pascal三角 （C语言代码）格式错误

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

回文数字 （C语言代码）

明明的随机数（C++代码）

【明明的随机数】（C语言代码）

【出圈】（C语言代码）用单项循环链表

　　评论区

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

Pascal三角（C语言代码）格式错误

回文数字（C语言代码）