sfs和dp例子

package com.od;

import java.util.Scanner;


public class Main0004 {
    public static int cnt = 0;

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int n = scanner.nextInt();
            dfs(0, n);
            System.out.println(cnt);
        }
    }

    
    private static void dfs(int cur, int n) {
        if (cur == n) {
            cnt++;
        }
        if (cur > n) {
            return;
        }
        dfs(cur + 1, n);
        dfs(cur + 3, n);
    }

    private static void solution(int n) {
        int step1 = 1, step2 = 1, step3 = 2;
        int step4 = n == 1 || n == 2 ? 1 : 2;
        for (int i = 4; i <= n; i++) {
            step4 = step3 + step1;
            step1 = step2;
            step2 = step3;
            step3 = step4;
        }
        System.out.println(step4);
    }
}

package org.example;

import java.util.Scanner;


public class Test33 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            System.out.println(walk(n, m));
        }
    }

    public static int walk(int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < dp[0].length; i++) {
            // 列长度
            dp[0][i] = 1;
        }

        for (int i = 0; i < dp.length; i++) {
            // 行长度
            dp[i][0] = 1;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[n][m];
    }
}

package org.example;

import java.util.Scanner;


public class Test34 {

    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(); // 苹果个数
        int n = in.nextInt(); // 盘子个数
        System.out.println(countWays(m, n));

        ///System.out.println(count(m, n));
    }

    // 动态规划
    public static int countWays(int m, int n) {
        // 额外创建一行作为辅助行
        int[][] dp = new int[m + 1][n + 1];
        // 初始化（m-n=0时，1种摆法）(n=1, 1种摆法【可省略】)
        for (int j = 0; j < dp[0].length; j++) {
            dp[0][j] = 1;
        }
        // 遍历计算f(m, n) = f(m, n-1) + f(m-n, n)
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i][j - 1] + (i < j ? 0 : dp[i - j][j]);
            }
        }
//          1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
//          2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，
//          即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
//          即求(m-n，n)
//          就转换为了以上两种情况
        return dp[m][n];
    }

    public static int count(int m, int n) {
        //不可能是负数
        if (m < 0 || n <= 0) {
            return 0;
        }
        // 细分为苹果数为1或盘子数为一的情况返回1
        //一个苹果、一个盘子、没有苹果，就都只有一种情况
        //给出了下限，1种1种的向上累计
        if (m == 1 || n == 1 || m == 0) {
            return 1;
        }
        // 将事件无线细分
        return count(m, n - 1) + count(m - n, n);
//          1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
//          2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
//          即求(m-n，n)
//          就转换为了以上两种情况
    }
}