网站设计与建设的公司,手工做皮具国外的网站,微网站建设渠道,制作网页多少钱文章目录 例题#xff1a;900. 整数划分解法1——完全背包解法2——分拆数⭐⭐⭐ 例题#xff1a;900. 整数划分
https://www.acwing.com/problem/content/902/
解法1——完全背包
容量是 n#xff0c;物品的大小和价值是 1 ~ n 中的所有数字。
import java.util.*;pub… 文章目录 例题900. 整数划分解法1——完全背包解法2——分拆数⭐⭐⭐ 例题900. 整数划分
https://www.acwing.com/problem/content/902/
解法1——完全背包
容量是 n物品的大小和价值是 1 ~ n 中的所有数字。
import java.util.*;public class Main {public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();final int MOD (int)1e9 7;int[] dp new int[n 1];dp[0] 1;for (int i 1; i n; i) {for (int j i; j n; j) {dp[j] (dp[j] dp[j - i]) % MOD;}}System.out.println(dp[n]);}
}解法2——分拆数⭐⭐⭐
状态表示 f[i][j]表示总和为i总个数为j的方案数
状态转移方程 f[i][j] f[i - 1][j - 1] f[i - j][j]; 从最小值 1 的转移过来就是补上数字1。 从最小值 1 的转移过来就是把每个数字都 1。
import java.util.*;public class Main {public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();final int MOD (int)1e9 7;// f[i][j]表示总和为i总个数为j的方案数int[][] dp new int[n 1][n 1];dp[1][1] 1;for (int i 2; i n; i) {for (int j 1; j i; j) {dp[i][j] (dp[i - 1][j - 1] dp[i - j][j]) % MOD;}}int ans 0;for (int j 0; j n; j) {ans (ans dp[n][j]) % MOD;}System.out.println(ans);}
}
