[珂苔]14-1次元ダイナミック

2 x nタイル

2 x n矩形の数を1 x 2、2 x 1タイルでどのように充填するか
次の図は、2 x 5の数を埋める方法を示しています.
D[n]=2 xn矩形の数をどのように埋めるか

の一番右のタイルは2つの形しかありません.

2 xn矩形がある場合、最も右側にタイルを置く方法は2つあります.

2 x n = D[n]

2 * n-1 = D[n-1]

2 * n-2 = D[n-2]
D[n] = D[n-1] + D[n-2]

2 x nタイル2

2個のn矩形の1個、2個、1個と2個の2個のタイルの充填数
D[n]=2 xn矩形の数をどのように埋めるか

右端:D[N-1]、D[N-2]、D[N-2]

D[N] = D[N-1] + D[N-2] * 2
=>式はこのようなものなので、上のコードで式を少し変えるだけです.

最後の一歩が何なのかを見て、それがないときの状況を考えてみましょう.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int d[]= new int[1001];
		d[0] = 1;
		d[1] = 1;
		for(int i=2;i<=n;i++) {
			d[i] = d[i-1]+d[i-2]*2;
			d[i] %= 10007;
		}
		System.out.println(d[n]);
	}
}

1、2、3を合わせる

これは以前に解いた問題で、ダイナミックプログラミングで再解答します.
整数nを求めて1、2、3の和を表す方法数の問題
ここで、整数nが1、2、3の和を表す方法数をD[n]と呼ぶ.
問題は1、2、3の和ということなので、最後に来た数は
1来るかもしれない、2来るかもしれない、3来るかもしれない.
最後が1であれば,前はn−1,+1,次いでnである.
最後に2であれば、n−2を前に作成し、+2でnを作成します.
最後が3の場合、前はn-3、それから+3、それからnです.
->n−1のすべての方法の数(D[n−1])に+1を加えるとnとなる.
n−2を作成するすべてのメソッドの数(D[n−2])に+2を追加するとnになります.
n−3を生成するすべての方法(D[n−3])に+3を加えるとnとなる.

D[n]=D[n-1]+D[n-2]+D[n-3].

定義

D[0]は、容易に符号化することができる.

0個の

を使用すると、1種類の->D[0]=1になります.

X質問に答える時間
点火式D[n]は一つの問題である.
D[n]=D[n−1]+D[n−2]+D[n−3]の時間的複雑度はO(1)*N=O(N)であった.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int d[]=new int[11];
		d[0]=1;
		for(int i=1;i<=10;i++) {
			for(int j=1;j<=3;j++) {
				if(i-j >= 0) {
					d[i] += d[i-j];
				}
			}
		}
		
		int t= sc.nextInt();
		for(int k=0;k<t;k++) {
			int n= sc.nextInt();
			System.out.println(d[n]);
		}
		
	}
}

購入カード

N枚のカードを購入する必要があります.
カードケースは全部でN種類あります.
i第1のカードバッグはi個のカードを含み、価格はP[i]元である.
N枚のカードを購入する最大コストの問題

カードパック、カードパック、カードパック=N
D[N]=N個のカードを購入する最大コスト.

最後に1つのカードバッグを買って、カードはN個になりました.

最後のカードパックにはいくつのカードがありますか?何枚目のカードパックですか?答えはわからない

の情報がダイナミックプログラミングにおける重要な情報であることを知らない.

を知らなければ、あらゆる方法を考えなければならない.

第1のカードパック=N個.

第2のカードパック=N個
.............

N第1のカードパック=N個

=>N種が最後に現れる可能性がある場合.
全部計算して最大値を求めればいいです.

では、問題は最大コストを求めることであるため、最大コストを得るだけでよい.

D[i]=購入カードiの最大コスト.

N-1枚のカードでD[N-1]を購入し、1枚目のカードパックでP[1]を購入し、N枚のカードを作成した.
=> D[N-1] + P[1]
N-2枚のカードを購入し、D[N-2]の2枚目のカードパックを購入し、P[2]でN枚のカードを作成します.
=> D[N-2] + P[2]
...
N個目のカードパックを購入して0個のカードを購入してN個を作る
=> D[0]+P[N]

カードをi個購入します.
(i-j)個のカードを購入した場合、->jは2番目のカードパック、i個のカードを作成します.
-> max( D[i-j] -> P[j] ) = D i

時間の複雑さ

すべての問題の個数*1つの問題を解くのに要する時間.

N * O(N) = O(N^2)

D[0]=カードパックを購入せずに済みます.つまり0が大きくなりました(初期値)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]=new int[n+1];
		
		for(int i=1;i<=n;i++) {
			a[i]=sc.nextInt();
		}
		int d[]=new int[n+1];
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=i;j++) {
				if(d[i] < d[i-j] + a[j]) {
					d[i] = d[i-j] + a[j];
				}
			}
		}
		System.out.println(d[n]);
	}
}

購入カード2

N枚のカードを購入する最低コストの問題.
maxじゃなくてminに変えればいい
この方法は配列dにおいて常に0である.
購入カードの料金が0より大きいので、minの結果はいつも0です.
したがって、初期値を設定する必要があります.

の値を非常に大きな値に入れます.可能な答えに最大値を入れます.(1000*10000)

の飲み物を入れます.(-1)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]=new int[n+1];
		
		for(int i=1;i<=n;i++) {
			a[i]=sc.nextInt();
		}
		int d[]=new int[n+1];
		for(int i=1;i<=n;i++) {
			d[i]=-1;
			for(int j=1;j<=i;j++) {
				if(d[i]==-1 || d[i] > d[i-j] + a[j]) {
					d[i] = d[i-j] + a[j];
				}
			}
		}
		System.out.println(d[n]);
	}
}

これは崔伯俊先生のコードテストの基礎科目に基づいて書いた文章です.