Chaim

用户名：YuQingming

访问量：3750

签　名：

欲善其事必先利器

等　　级
排　　名	540
经　　验	4432
参赛次数	3
文章发表	8
年　　龄	19
在职情况	学生
学　　校	HBNU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

【滑动窗口】数组求和-题解（Java代码）
浏览：610

你可能喜欢

蓝桥杯算法提高VIP-摆花-题解（Java代码）

　　作者: Chaim　　　　发表时间：2020-06-07 18:35:30 浏览：282　|　评论：0　

原题链接：蓝桥杯算法提高VIP-摆花

【方法一】：动态规划（二维数组）

```java
import java.util.Scanner;

/**
 * @author Administrator
 */
public class Main {
    /** 条件限制：第i种花最多放limit[盆] */
    static int[] limit;

/** 动态规划，dp[i][j]代表有i种花，j盆的放法个数 */
    public static int dp(int n, int m){
        int[][] dp = new int[n + 1][m + 1];
        // 初始化
        // 如果只能放0盆花，只有一种放法
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
        }
        // 如果只有一种花，只有一种放法
        for (int i = 0; i <= limit[1]; i++) {
            dp[1][i] = 1;
        }
        // 递推
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 有i种花共j盆的放法是有i-1种花情况的放法累加之和
                for (int k = 0; k <= limit[i] && k <= j; k++) {
                    dp[i][j] += dp[i - 1][j - k];
                    // 题目要求存放余数
                    dp[i][j] %= 1000007;
                }
            }
        }
        return dp[n][m];
    }

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        limit = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            limit[i] = scanner.nextInt();
        }
        System.out.print(dp(n, m));
    }
}
```

普通的动态规划已经能够通过判题系统，在代码里注意到dp[i][j]与只与d[i-1][j]有关，因此这个题目可以用滚动数组(一维)来解决，同样属于动态规划

【方法二】动态规划（滚动数组）

一层一层的滚动，更新数据

更新前是上一层的数据(dp[i-1][j])，更新后是当前层的数据(dp[i][j])

```java
import java.util.Scanner;

/**
 * @author Administrator
 */
public class Main {
    /** 条件限制：第i种花最多放limit[盆] */
    static int[] limit;

/** 用滚动数组 */
    public static int dp(int n, int m){
        int[] dp = new int[m + 1];
        // 初始化
        dp[0] = 1;
        // 一层一层递推
        for (int i = 1; i <= n; i++) {
            // 必须反过来排
            for (int j = m; j >= 1; j--) {
                for (int k = 1; k <= limit[i] && k <= j; k++) {
                    dp[j] += dp[j-k];
                    dp[j] %= 1000007;
                }
            }
        }
        return dp[m];
    }

参考：http://yuhang.site/?p=1539

0.0分

1 人评分

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

Chaim

TA的其他文章

你可能喜欢

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

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

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

C语言训练-求PI* （C语言代码）

C语言训练-阿姆斯特朗数（C语言代码）

蓝桥杯算法提高VIP-摆花-题解（Java代码）

评论区

精彩推荐

母牛的故事（C语言代码）

川哥的吩咐（C语言代码）

剔除相关数（C语言代码）

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

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

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

【亲和数】（C语言代码）

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

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

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

Chaim

TA的其他文章

你可能喜欢

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

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

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

C语言训练-求PI* （C语言代码）

C语言训练-阿姆斯特朗数 （C语言代码）

蓝桥杯算法提高VIP-摆花-题解（Java代码）

评论区

精彩推荐

母牛的故事 （C语言代码）

川哥的吩咐 （C语言代码）

剔除相关数 （C语言代码）

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

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

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

【亲和数】 （C语言代码）

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

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

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-阿姆斯特朗数（C语言代码）

　　评论区

母牛的故事（C语言代码）

川哥的吩咐（C语言代码）

剔除相关数（C语言代码）

【亲和数】（C语言代码）