動的プログラミングは、ほとんどのソフトウェアエンジニアの悩みの種かもしれません。 5042>
面接官はこのような質問をするのが好きですが、それは難しいからです。
面接官は、DP問題にアプローチするための問題解決のフレームワークを持っていないので、本当に苦労します。 他の DP 問題で見たパターンを適用することはできないのです。なぜなら、DP 問題はまったく違って見えるからです。
この投稿では、より良い方法をお見せしたいと思います。以下のビデオでは、面接で見られることが予想される、最も一般的な DP 問題のうち 6 つについて説明します。 これらの問題を学び、FASTメソッドを適用する方法を学べば、面接でダイナミックプログラミングに取り組むのに非常に有利な状態になります。
ヒント: まだ動的計画法の初心者であれば、まず42ページの無料の電子書籍「面接のための動的計画法」をご覧ください
問題をチェックする:
Smallest Change
釣り銭の入力金額 x がある場合、その金額を作るために最小限の硬貨数を決定する関数を書け
eg. (アメリカンコインを使用)
|
1
2
3
4
|
change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
2つの文字列が与えられたとき。 最も長い共通部分文字列を返す関数を書きなさい。
eg.
longestSubstring("ABAB", "BABA") = "ABA"
フィボナッチ数
整数nが与えられたら、n番目のフィボナッチ数を計算する関数を書け。
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Square Submatrix
1 と 0 の2次元配列が与えられたら、すべての 1 の最大の正方形部分配列を求めよ。
|
1
2
3
|
subarray(
) = 2
|
Matrix Product
行列が与えられた。 左上から右下へ、下と右にだけ移動して積が最大となる経路を求めよ。
eg.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
1 -> 4 -> 7 -> 8 -> 9
2016
-1 -> 4 -> 5 -> -6 -> 9
1080
|
0-1 ナップザック
値と重みのある項目のリストが与えられたとき。 と重みの最大値から、重みの合計が最大値より小さい項目から生成できる最大値を求めよ。
eg.
|
1
2
3
|
items = {（w:1, v:6）, (w:2, v:10), (w:3, v:12)} ｝となる。
maxWeight = 5
knapsack(items, maxWeight) = 22
|