蓝桥杯算法提高vip- 数的划分 -java

解题思路:

按照每组数字划分中最大的数字进行分组

1

1,1  2   

1,1,1  2,1  3

1,1,1,1  2,1,1,  2,2  3,1  4

1,1,1,1,1  2,1,1,1  2,2,1  3,1,1  3,2  4,1  5

1,1,1,1,1,1  2,1,1,1,1  2,2,1,1  2,2,2  3,1,1,1  3,2,1  3,3  4,2  4,1,1  5,1  6

用二维数组存储,每个数字中出现的次数

1

1  1

1  1  1

1  2  1  1

1  2  2  1  1

1  3  3  2  1  1

总结规律：

第一个和最后一个都是1，中间的：dp(i,j) = dp(i-j,j) + dp(i-1, j-1)

注意事项:

参考代码:

import java.util.Scanner;

/**
 * @BelongsProject Demo
 * @BelongsPackage PACKAGE_NAME
 * @Author lgb
 * @CreateTime 2022-06-09  22:05
 * @Description TODO
 * @Version 1.0
 */
public class Main {

    public static void main(String[] args) {
        //输入
        Scanner scanner = new Scanner(System.in);
        //拆分的数字
        int n = scanner.nextInt();
        //一个数组存储一个数字的拆分信息
        int[][] dp = new int[n+1][n+1];
        //1-n,每组数字划分最多只有n个数组合的。如5， 只能是 1 2 3 4 5 这5个数，不可能还有6
        //大循环，总共循环 n 次
        for (int i=1; i <= n; i++) {
            //小循环，每次都是一组数据
            for (int j=1; j<=i; j++) {
                //判断是否是第一个和最后一个
                if (j ==1 || j==i) {
                    dp[i][j] = 1;
                } else {
                    //这个规律能找出来的真神人，这个不是我找出来的
                    dp[i][j] = dp[i-j][j] + dp[i-1][j-1];
                }
            }
        }
        int sum = 0;
        for (int i : dp[n]) {
            sum += i;
        }
        System.out.println(sum);
        //关闭
        scanner.close();
    }
}