[アルゴリズム]-白準15988号:1、2、3プラス3(JAVA)

9764 ワード
Java algorithm テキストリンク

🎯 質問する


質問元:白峻15988号。

🚀 解答方法


まず問題を見ましょう.
問題は,与えられた整数を1,2,3の和として表す方法数を求めることである.
問題の例は、4が1、2、3の和であることを示します.
1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 2+1+1
5. 2+2
6. 1+3
7. 3+1
全部で7種類あります.
1、2、3の数字は同じですが、順番が違う場合も違う場合の数字と混同してはいけません!
ex)1+1+2と1+2+1,2+1+1,2+1+1が互いに認め合う場合
点火式を導き出しましょう!
1,2,3の和で4を表す方法を見てみましょう.
黒体字は出現可能な場合を表し、赤体字は所定の整数を導出するのに必要な数(1、2、3の1つ)を表す.
  • 1を表すことができる場合は、で4を作成します.
  • 1+3
  • 2で4を作成する方法
  • 1+1+2
  • 2+2
  • 3で4を作成する方法
  • 1+2+1
  • 2+1+1
  • 1+1+2
  • 3+1
    • [点火式]
    dp[1]=1
    dp[2]=2
    dp[3]=4
    dp[n]=dp[n-1]+dp[n-2]+dp n-3を導出し、問題条件に応じて出力を1000000009に分割する.
    👏 最終的に.
    (n>=4)
    dp[n]=(dp[n-1]+dp[n-2]+dp[n-3])%1,000,000,009

    🚀 CODE

    import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception{
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int t=Integer.parseInt(st.nextToken());
        long[] dp=new long[1000001];
        List<Long> res=new ArrayList<>();

        dp[1]=1;
        dp[2]=2;
        dp[3]=4;

        for(int i=1;i<=t;i++){
            st=new StringTokenizer(br.readLine());
            int temp=Integer.parseInt(st.nextToken());
            
            for(int j=4;j<=temp;j++){
                if(dp[j]==0)
                    dp[j]=(dp[j-2]+dp[j-1]+dp[j-3])%1000000009;
            }
            res.add(dp[temp]%1000000009);
        }

        for (Long result : res) {
            System.out.println(result);
        }
    }
}

    以上が私たちのヒントですありがとうございます👋

    データ分析用のライブラリ.1
    CSS単位