[白俊2193-李親水-Java]

もんだいぶんせき

DP

時間の複雑さ

DPはO(N)問題を解決できる

インプリメンテーション

1.テーブルの定義

long[][] T = new long[100+1][2+1];
// T[N][1] -> N번째 자리 수 중에서 마지막이 1로 끝나는 이친수.
// T[N][0] -> N번째 자리 수 중에서 마지막이 0으로 끝나는 이친수.

2.点火式を得る

for(int n = 3; n <= N; n++){
	T[n][0] = T[n-1][0] +T[n-1][1];
    //  n-1번째 자리 수에서 끝자리가 0,1로 끝나는 수 모두에 0을 붙여서 n번째 자리 수를 만들 수 있다.
	T[n][1] = T[n-1][0];
    //  n-1번째 자리 수에서 끝자리가 0으로 끝나는 수에만 1을 붙여서 n번째 자리 수를 만들 수 있다.
}

3.初期値の設定

T[1][1] = 1;
T[1][0] = 0;

T[2][1] = 0;
T[2][0] = 1;

さまよう部分

データ型選択エラー.longを使うべきでしたがintを使いました.

その他の方法

テーブルをT[N]:N番目のビット数の親数値の個数として定義すると、T[N]=T[N−1]+T[N−2]となる.
T[N-1]:N-1桁の後ろに「0」を付けて、N桁目の定数を作成します.
T[N−2]:N−2桁の後ろに「01」を付けると,N桁目のこの定数を作成できる.
すなわち,フィボナッチ数列のような形式の点火式が得られる.

取得する

DPに対する感覚を失わないでください.

完全コード[マイコード-Java]

マイjavaコード

に感銘を与える

問題を解く時、論理は正しいと感じたが、いつも間違いばかりで悩んでいた.
結局答えしか見えませんでしたが、int型の資料型を使っていたので、間違っていたことに気づきました.
点火式を見て一般項目を導き出すことで資料型の大きさを推測できるが、実戦でできるかどうか疑問だ.
実際にこれらの問題に遭遇した場合、データ型の選択に問題があることを発見するのは難しいかもしれませんが、私の論理は確かに完璧ですが、エラーが発生した場合、データ型の問題であるかどうかを考慮する必要があることを経験しています.

リファレンス

問題のソース