当前位置：首页 > backend >正文

博客打卡-小易喜欢的数列-动态规划

backend 2025/5/1 23:41:47

题目如下：

小易喜欢的数列有以下性质的数列

（1）数列的长度为n。

（2）数列中的每个数都在1到k之间（包括1和k）。

（3）对于位置相邻的两个数A和B（A在B前），都满足A<=B或A MOD B != 0（满足其一即可）。

例如，n=4，k=7，那么{1，7，7，2}，它的长度是4，所有数字也在1到7的范围内，并且满足性质（3），所以小易是喜欢这个数列的。但是小易不喜欢{4，4，4，2}这个数列。小易给出n和k，希望你能帮他求出有多少个是他喜欢的数列。

输入格式:

输入包括两个整数n和k（1<=n<=10,1<=k<=10000）。

输出格式:

输出一个整数，即满足要求的数列个数，因为答案可能很大，输出对1 000 000 007取模的结果。

输入样例:

在这里给出一组输入。例如：

2 2

输出样例:

在这里给出相应的输出。例如：

解题思路如下：

题目要求给出符合条件的数列的个数，我们可以通过动态规划方法计算结果。设dp[i][j] 表示长度为 i 且最后一个数为 j 的合法数列的个数。对于长度为 i 的数列，设最后一个数为 j，倒数第二个数为 p。由于题目要求需要满足 p <= j 或 p % j != 0。因此，为了确定dp[i][j]，我们将在dp[i][j]的基础上，遍历所有长度为i-1，末尾为从1到k之间的数字p，满足题目条件的dp[i-1][p]，得到dp[i][j] = (dp[i][j] + dp[i - 1][p]) % MOD。

代码如下：

import java.util.Scanner;public class Main {private static final int MOD = 1_000_000_007;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int k = scanner.nextInt();long[][] dp = new long[n + 1][k + 1];// Initialize base case: sequences of length 1for (int j = 1; j <= k; j++) {dp[1][j] = 1;}// Fill the dp tablefor (int i = 2; i <= n; i++) {for (int j = 1; j <= k; j++) {dp[i][j] = 0;for (int p = 1; p <= k; p++) {if (p <= j || p % j != 0) {dp[i][j] = (dp[i][j] + dp[i - 1][p]) % MOD;}}}}long result = 0;for (int j = 1; j <= k; j++) {result = (result + dp[n][j]) % MOD;}System.out.println(result);scanner.close();}
}

提交结果如下：