【蓝桥杯/动态规划】数的计算

发布时间:2024年01月15日

数的计算

题目描述

输入一个自然数 n?(n≤1000)n\ (n \leq 1000)n?(n1000),我们对此自然数按照如下方法进行处理:

  1. 不作任何处理;

  2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;

  3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止。

问总共可以产生多少个数。

输入描述

输入一个正整数 nnn

输出描述

输出一个整数,表示答案。

输入输出样例

示例 1

输入

6
copy

输出

6

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int[] arr=new int[n+1];
        arr[0]=arr[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=0;j<=i>>1;++j){
                arr[i]+=arr[j];
            }
        }
        System.out.println(arr[n]);
        scan.close();
    }
}
文章来源:https://blog.csdn.net/JeredYe/article/details/135605957
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。