[プログラマー]#12902 x nタイル

4176 ワード
プログラマ DP テキストリンク

質問する


長方形のタイルがあり、横方向の長さは2、縦方向の長さは1です.この矩形タイルを用いて床を充填し,床の長手方向長さは2,横方向長さはnである.タイルを充填するには2つの方法があります.
  • タイルを水平に置く場合は
    • である.
  • タイル垂直置き時は
    • 例えば、nが7の矩形を以下のように充填することができる.

    矩形の横方向の長さnをパラメータとして指定した場合、解関数を完了し、矩形を埋め込む方法の数を返します.

    せいげんじょうけん

  • 街の長さnは60000以下の自然数である.
  • の場合の数が多くなる可能性があります.状況の数を100000007で割って返してください.

    • I/O例


    nresult45

    I/O説明


    5つの方法があります.





    に答える


    この問題は動的プログラミング(DP)で解決できる.a=an,1+an,2 a n=a n−1}+a n−2}a=an,1+an,2点和式で解くことができる.
    class Solution {
    public int solution(int n) {
        
        if(n==1) return 1;
        
        int[] dp = new int[n+1];
        
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i=2; i<=n; i++)
            dp[i] = (dp[i-1] + dp[i-2])%1000000007;
        
        
        return dp[n];
    }
}
    画像の自動スケーリングを制限範囲で実現
    javaweb_フォームの中央揃え