Contents
最長増加連続部分列
最長増加連続部分列とは、配列があったとき単調増加になっている最も長い部分です。配列が {1, 2, 3, 4, 5} であるなら配列全体が単調増加しているので求める解は {1, 2, 3, 4, 5} です。配列が {10, 2, 3, 5, 7, 1, 4, 6} であれば {2, 3, 5, 7} が求める解ということになります。
最長増加連続部分列の長さ
配列 a を {10, 2, 3, 5, 7, 1, 4, 6}とする場合、a[k] までの単調増加部分の長さをdp[k]とすると dp[k] と dp[k-1]のあいだには関係があることがわかります。
もし a[k] と a[k – 1] が a[k] ≦ a[k – 1] であるなら dp[k] は dp[k-1] より1多くなります。 a[k] ＞ a[k – 1] であるなら単調増加が続いている状態は終わってしまうので dp[k] は 1 に戻ってしまいます。
|
1 2 3 4 |
if(a[k-1] <= a[k]) dp[k] = dp[k-1] + 1; if(a[k-1] > a[k]) dp[k] = 1; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public class Program { static void Main() { int[] a = { 10, 2, 3, 5, 7, 1, 4, 6 }; int n = a.Length; int[] dp = new int[n]; dp[0] = 1; for (int i = 1; i < n; i++) { if (a[i - 1] <= a[i]) dp[i] = dp[i - 1] + 1; else dp[i] = 1; } // dp をデバッグのために表示させる string str = string.Join(", ", dp); Console.WriteLine(str); Console.WriteLine($"最長増加連続部分列の長さは{dp.Max()}"); } } |
最長増加部分列
n 本の木が横一列に並んでいます。あなたは何本かの木を伐採することによって、残った木を左から順に見ると高さが単調増加になっているようにしたいと考えています。なるべく多くの木が残るように伐採する木を工夫して選んだとき、伐採されずに残る木の本数がいくつになるでしょうか？
これは最長増加部分列の問題です。増加部分列とは、ある与えられた長さの数列からいくつかの値を順番を変えずに取り出したときに、これが単調増加する配列のことです。そのなかでも長さが最長になる増加部分列を最長増加部分列といいます。
配列が {3, 6, 4, 2, 7, 8} であれば {3, 6, 7, 8} が求める解ということになります。今度は最長増加連続部分列とは異なり連続している必要はありません。連続していなくていいのでいくつかピックアップしてそれらが単純上昇していればよいのです。
ここではdp[k] を a[k] までも増加部分列のうち最長であるものの長さと考えます。もし dp[0] から dp[k-1] が求まっているとして dp[k] とこれらの関係はどのようになっているでしょうか？
0 ≦ i ≦ n – 1 において a[i] < a[n] が成り立っているとき、最後がa[i]になっている増加部分列の最後にa[n] をくっつけることで、dp[n] + 1 の増加部分列を作れることがわかります。そしてこのようにして作られる部分列のうち最長のものが、いま求めようとしている最長増加部分列です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static void Main() { int[] a = { 3, 6, 4, 2, 7, 8 }; int n = a.Length; int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i]) dp[i] = Math.Max(dp[i], dp[j] + 1); } } Console.WriteLine("最長増加部分列の長さは" + dp.Max()); // 配列の長さが k のときの最長増加部分列の長さ Console.WriteLine(string.Join(", ", dp)); } } |
部分和問題
これは部分和問題です。部分和問題とは、与えられた n 個の整数のなかから部分集合をうまく選んで、その集合内の数の和を与えられた数 N に等しくできるかどうかを判定する問題です、計算複雑性理論・暗号理論にも使われる問題です。
部分和が指定された値になるか？
1 ～ n の番号がついた n 個の重りがある。重りを何個か選んで重さの和が x となるようにすることができるかどうか判定してください。ただし同じ重りを複数個選ぶことはできません。
動的計画法では以下のように考えます。
番号 n – 1 までのおもりを用いて重さの和がすでに x になっているか、つぎに番号 n の重りを追加すれば重さが x になる場合は重さの和を x にすることができます。
配列 a[k]を k 番目の重りの重さ、配列 dp[x] を重さの和が x になるかの真偽値とすることで問題を解くことができそうです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static void GetResult(int[] weights, int x) { int n = weights.Length; bool[] dp = new bool[x + 1]; dp[0] = true; for (int i = 0; i < n; i++) { for (int k = x; k >= weights[i]; k--) { if (dp[k - weights[i]]) dp[k] = true; } } Console.WriteLine(string.Join(", ", weights)); if (dp[x]) Console.WriteLine("できる"); else Console.WriteLine("できない"); } static void Main() { GetResult(new int[]{ 7, 18, 5, 4, 8}, 19); GetResult(new int[] { 7, 18, 5, 4, 8 }, 21); } } |
組み合わせは何通りあるか？
次に重りを何個か選んで重さの和を x にする方法が何通りあるかを求めます。ただし同じ重りを複数個使うことはできません。同じ重さの重りが複数存在する場合、それらは別物として扱います。
重り k までを用いて重さの和が x となるような選び方がすでに求まっているなら重り k + 1 までを用いて重さの和を x となるような選び方も求めることができます。
漸化式は以下のようになります。
dp[x] = dp[x – weights[k]] + dp[x]
一次元配列を使う場合は配列の後ろから値を更新しないと正しい結果が得られません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public class Program { static void GetResult2(int[] weights, int x) { int n = weights.Length; int[] dp = new int[x + 1]; dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = x; j >= weights[i]; j--) dp[j] += dp[j - weights[i]]; } Console.WriteLine($"合計：{x} ({string.Join(", ", weights)})"); Console.WriteLine($"{dp[x]} とおり"); } static void Main() { GetResult2(new int[]{ 7, 3, 4, 3, 2 }, 10); GetResult2(new int[] { 1, 2, 3, 4, 5, 6 }, 10); } } |
選択する数の最小値は？
重りを何個か選んで重さの和が x となる場合で、選ぶ重りの個数が最小値になるようにするにはどうすればいいでしょうか？
重り k までを用いて重さの和が x となるように重りを選ぶときの個数の最小値が求まっていれば、そこから重り k + 1 までを用いて重さの和を x となるように選ぶときの個数の最小値を求めることができます。
重り k までを用いて重さの和が x となるように重りを選ぶときの個数の最小値は（k – 1 までを用いて重さの和が x となるときの最小個数）と（k – 1 までを用いて重さの和が x – weights[k] となるときの最小個数に1を追加したとき）のなかで少ない方です。
最初は dp[0] 以外の要素に ∞ を入れておきます。dp[k – weights[i]]が∞のときはおもりを選ぶ方法が存在しないのでスキップします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static void GetResult3(int[] weights, int x) { int n = weights.Length; int[] dp = new int[x + 1]; dp[0] = 0; for (int i = 1; i <= x; i++) dp[i] = int.MaxValue; for (int i = 0; i < n; i++) { for (int k = x; k >= weights[i]; k--) { // 重さ k になるような選び方は存在しないのでスキップする if (dp[k - weights[i]] == int.MaxValue) continue; dp[k] = Math.Min(dp[k], dp[k - weights[i]] + 1); } } Console.WriteLine($"合計：{x} ({string.Join(", ", weights)})"); if(dp[x] != int.MaxValue) Console.WriteLine($"最低必要個数は {dp[x]}"); else Console.WriteLine("不可能"); } static void Main() { GetResult3(new int[]{ 7, 3, 4, 3, 2 }, 10); GetResult3(new int[] { 2, 4, 6, 8, 10 }, 21); } } |
