Dinamik Programlama özyinelemeli veya yinelemeli

Question

Dinamik Programlama hakkında bilgi edindim ve oldukça yeni. Dinamik Programlamanın “yinelemeli” ve “özyinelemeli” bir şekilde uygulanıp uygulanamayacağını ya da sadece bu yöntemlerden birini uygulamak için iyi bir uygulama olduğunu bilmek istedim. İyi örnekler/bağlantılar yardımcı olabilir.

Answer 1

Evet, DP her ikisine de uygulanabilir.

buradan başlayın

: Sonra uygulama için problemleri (bu sorunların her biri ayrıca bir Editorial fikir açıklayan var TopCoder.com sen bağlantılar bulacaksınız, Dynamic Programming: From novice to advanced ve ilk eğitim için

A Tutorial on Dynamic Programming sahip http://en.wikipedia.org/wiki/Dynamic_programming

çözelti geride.

Answer 2

Dinamik programlama ters uygulanan yinelemeli bir çözelti olarak (birçok durumda) görülebilir.

K Bir özyinelemede, (veya başka bir değer) için bazı durma koşuluyla x(n+1) = f(x(n)) değerini hesaplarsınız. Çoğu durumda f işlevi, min/max işlevinin bir işlevidir, ancak olması gerekmez. Ayrıca, fonksiyonun tek bir değişken alması gerekmiyor.

Dinamik programlama birden fazla değişkeni sonra, f(1) sonra f(2) vb

f(0) hesaplayarak bu problemi çözecek, normalde fonksiyonunu hesaplamak için bazı doğal düzen olmazdı.

Dinamik programlamanın çözebileceği bir örnek: Size 3 golf sopası verilir. Her golf kulübü bir golf topu x ileri mesafe gönderebilir (örneğin, 24, 37 ve 54 adet). Soru şu: tam olarak 200 birim uzakta olan bir deliğe çarpar mısınız? Ve eğer yapabiliyorsanız, ihtiyacınız olan minimum çekim sayısı. n 0 ise fonksiyon shot(n) döner, bazı büyük sayı n 0'dan düşükse 0, bu önemsiz bir uygulanmasına olanak sağlayacak

shots(200) = min(shots(200-24),shots(200-37),shots(200-54)) 

, ve ifadeyi:

özyinelemeli çözüm gibi bir şey olurdu aksi takdirde. Bununla birlikte, n'nin büyük değerleri için, yukarıdaki ifadenin farklı dallarından aynı değerleri tekrar ve tekrar vuracaksınız. Bu durumda, sadece 0'dan başlamak ve shots(0), shots(1), shots(2) hesaplamak daha iyidir. Bu, bu problemin "dinamik programlama" çözümü olabilir - üstel zaman yerine doğrusal zaman ve sabit alan (3 yollu bir ağaçtan geçerek)) ve en iyi doğrusal boşluk (çağrı yığını için).