java 90分求助

paceandhealthy @ 2023-03-27 17:50:58

public class Main
    public static void main(String[] args) throws IOException {
        StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter printWriter = new PrintWriter(new OutputStreamWriter(System.out));
        int n;
        streamTokenizer.nextToken();
        n=(int)streamTokenizer.nval;
        BigInteger dp[]=new BigInteger[n+1];
        dp[0]=BigInteger.valueOf(0);dp[1]=BigInteger.valueOf(1);dp[2]=BigInteger.valueOf(2);
        for (int i = 3; i <= n; i++) {
            dp[i]=dp[i-1].add(dp[i-2]);
        }
       printWriter.println(dp[n]);
        printWriter.flush();
    }
}

by SadlerCS @ 2023-05-10 04:46:48

你这里n = 1的时候, 给dp[2]复制, 数组越界了

对前面的值进行特判,这样就行了

import java.io.*;

import java.math.*;

import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter printWriter = new PrintWriter(new OutputStreamWriter(System.out));
        int n;
        streamTokenizer.nextToken();
        n=(int)streamTokenizer.nval;
        if (n <= 3) {
            printWriter.println(n);
            printWriter.flush();
            return;
        }
        BigInteger dp[]=new BigInteger[n+1];
        dp[0]=BigInteger.valueOf(0);dp[1]=BigInteger.valueOf(1);dp[2]=BigInteger.valueOf(2);
        for (int i = 3; i <= n; i++) {
            dp[i]=dp[i-1].add(dp[i-2]);
        }
       printWriter.println(dp[n]);
        printWriter.flush();
    }
}

by SadlerCS @ 2023-05-10 04:47:56

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    ////////////////////静态变量///////////////////////////

    static final int N = (int) (5e3 + 10), INF = 0x3f3f3f3f;
    // static int arr[] = new int[N];
    // static int q[] = new int[N];
    // static int arr[][] = new int[N][N];
    // static char g[][] = new char[N][N];
    // static boolean st[][] = new boolean[N][N];
    static int n, m, t;
    static int res, ans;

    static BigInteger dfs(int x) {
        if (x == 1) return BigInteger.ONE;
        else if (x == 2) return BigInteger.valueOf(2);
        else return dfs(x - 1).add(dfs(x - 2));
    }

    ////////////////////静态方法///////////////////////////
    // 01 暴力dfs(超时
    static void solve01() {
        BigInteger res = dfs(n);
        out.println(res);
    }

    static BigInteger mem[] = new BigInteger[N];

    static BigInteger memdfs(int x) {
        if (!mem[x].equals(BigInteger.ZERO)) return mem[x];
        BigInteger sum = BigInteger.ZERO;
        if (x == 1) sum = BigInteger.ONE;
        else if (x == 2) sum = BigInteger.valueOf(2);
        else sum = dfs(x - 1).add(dfs(x - 2));
        mem[x] = sum;
        return sum;
    }

    // 02 记忆化搜索(超时
    static void solve02() {
        if (!mem[n].equals(BigInteger.ZERO)) {
            out.println(mem[n]);
            out.flush();
            return;
        }
        BigInteger res = memdfs(n);
        out.println(res);
    }
    static BigInteger f[] = new BigInteger[N];

    // 03 递推
    static void solve03() {
        if (!f[n].equals(BigInteger.ZERO)) {
            out.println(f[n]);
            out.flush();
            return;
        }
        f[1] = BigInteger.ONE;
        f[2] = BigInteger.valueOf(2);

        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1].add(f[i - 2]);
        }
        out.println(f[n]);
    }

    // 04 空间优化
    static void solve04() {

        BigInteger newf = BigInteger.ZERO, tmp1 = BigInteger.ONE, tmp2 = BigInteger.valueOf(2);
        for (int i = 3; i <= n; i++) {
            newf = tmp1.add(tmp2);
            tmp1 = tmp2;
            tmp2 = newf;
        }
        out.println(newf);
    }

        //////////////////写解决方法/////////////////////////////
    static void solve() {
        Arrays.fill(f, BigInteger.ZERO);
        Arrays.fill(mem, BigInteger.ZERO);
        while (sc.hasNext()) {
            n = sc.nextInt();
            // 1 2 3 5
            if (n <= 3) {
                out.println(n);
                out.flush();
                continue;
            }

            // solve01();
            // solve02();
            // solve03();
            solve04();

            out.flush();
        }
        out.flush();
    }

    static void solveCom() { // 不需要 hasNext()
        int n = sc.nextInt();

        out.flush();
    }

    static void solveSub() { // t 次
        t = sc.nextInt();
        while (t-- > 0) {

            out.flush();
        }
        out.flush();
    }

    static void solveScan() { // 需要 hasNext()
        solve();

        out.flush();
    }

    public static void main(String[] args) throws Exception {
        /* 调用solve方法,好处是有多个题解可以写n个solve方法 */
        // solveCom();
        // solveSub();
        solveScan();

        // 最后清空并关闭输出流
        out.flush();
        out.close();
    }

    static PrintWriter out = new PrintWriter(System.out); // 输出流, 输出完之后记得用 out.flush() 清空一下缓存区
    static FastReader sc = new FastReader();

    ///////封装快速读取类的方法(基于Scanner的方法来写)/////////
    static class FastReader { // 输入类
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        boolean hasNext() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String line = br.readLine();
                    if (line == null) return false;
                    st = new StringTokenizer(line);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return true;
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        double nextDouble() { return Double.parseDouble(next()); }

        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }
    }
}