This time, I would like to focus on a category of problems almost as simple as the previous ones, but for which you will have to resort to dynamic programming in order to solve them. If you do not know what dynamic programming is, here's the definition from Wikipedia:

In mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of overlapping subproblems and optimal substructure.Let's take the simple example of the Fibonacci numbers. The n

^{th}number of Fibonacci, is defined by the recurring function F

_{n}= F

_{n-1}+ F

_{n-2}, with F

_{0}= 0 and F

_{1}= 1. Implementing such a function is very simple in any language, but unfortunately it is impractical due to performance issues. Indeed, the complexity of this algorithm is exponential. Thus, trying to compute values after F

_{30}starts to take a lot of time...

By writing on paper the process to compute a small Fibonacci number such as the 5

^{th}one, you would quickly notice that intermediate values are computed several times, which is a loss of time. This is where dynamic programming comes to our help!

A first approach, the bottom-top one, would be to always remember F

_{n-1}and F

_{n-2}, starting with 0 and 1. Then, we would compute the next value, and store it as the new F

_{n-1}, and shift the previous F

_{n-1}in F

_{n-2}. Repeating this process until F

_{n}would give us its value in time complexity O(n), which is far better than the exponential complexity of the naive implementation we saw before. Here's how you could implement this approach using Clojure lazy infinite sequence:

Now that we have an efficient implementation of the Fibonacci sequence, the solution to problem 2 is straightforward:

Another approach to the Fibonacci function implementation is the top-bottom one. This approach basically consist in memoizing intermediate results so that they can be reused in later steps of the computation. Language such as Factor make this really easy, by providing native support of memoization with the keyword MEMO:, as you can see in the following code:

We can now make use of this function in order to solve problem 25 with the following code:

Now that we saw how dynamic programming could be used to solve trivial problems related to recursively defined number such as Fibonacci numbers, let's take a more interesting example with the problem 81, explained as follows:

Considering the previous matrix as a graph, each cell being a node, and each possible right or down move being the edges, this problem becomes a shortest-path problem.In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

Find the minimal path sum, in matrix.txt, a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

A naive approach would be to try every single path... and if you already solved the problem 15, you would know that there are 160!/(80!80!) of them! For information, it is a 47-digit number.

Obviously using this naive algorithm is a wrong way, as it doesn't scale at all.

But again, this is a field where dynamic programming can help us a lot, with Dijkstra's algorithm. This algorithm is a form a dynamic programming, as it calculates the shortest path from an intermediate node to another node reusing the previously calculated shortest path from the start node to this intermediate node.

Having the graph data as a matrix stored in a variable m, the implementation is quite obvious in Ruby:

Finally, the shortest path is given by the accumulated value in most the bottom right cell (m[79][79]).

We saw in this post how dynamic programming can radically improve the performance of certain type of algorithms, which wouldn't scale at all on large data sets. This method can be applied to several Project Euler challenges, as we saw in problems 2, 25 and 81. The basic way of proceeding is to find sub-problems which can reuse intermediate results leading naturally to the final result.

In the next post, I will introduce other general approach that can be used to solve Project Euler challenges.

很喜歡你的blog哦...加油唷 ........................................

ReplyDeletea片子安心亞寫真top1069拓網交友做愛自拍免費情色影片383成人台灣情網影片線上免費av18禁250av女優免費影片旺來出品辣妹寫真鋼管秀bt旺來出品辣妹寫真鋼管秀旺來風情寫真秀-辣妹過招旺來風情寫真秀旺來蓬萊仙山寫真集 vcd旺旺仙貝的狂想境地早洩韭南籽早期歐美a片早期范冰冰照片早春小老婆美女 視訊youtube 影片g世代論壇080視訊聊天室aaaaa片俱樂部影片微風成人情色 網18禁地少女遊戲女生自衛影片免費聊天女同志聊天室成人聊天室性愛日記網交聊天室性愛姿勢免費av影片觀看拓峰交友美女聊天室hbo論壇一夜情視訊聊天室五分鐘護半身視訊美女激情網愛聊天室

ReplyDeletethank you for you to make me learn more,thank you∩０∩ ........................................

ReplyDeletewonderful...................................................

ReplyDelete我們唯一需要恐懼的事，是恐懼本身........................................

ReplyDeleteI love readding, and thanks for your artical.........................................

ReplyDelete從人生中拿走友誼，猶如從生活中移走陽光........................................

ReplyDelete成人無碼片線上看18限成人影片論壇成人鴛鴦成人影片鴛鴦吧成人影片a正妹百人斬a影片免費看a騙bbsx693bonbonme線上觀看bt成人分享bt免費論壇bt後宮cb 倉井空影片cb倉井空影片cf聊天室dudu貼片dudu嘟嘟區dvd 卡通色情片a影片卡通a網情色片a漫網址a色情圖片a免費卡通影片a免費看片a免費情色影片a免費影片觀看a免費線上直播a免費線上觀賞a我愛78論壇視訊辣妹亞洲情色風暴貼圖交友聊天找e爵aio交友愛情館

ReplyDelete忙碌的一天終於過了，來看看文章轉換心情，也幫你加個油哦~........................................

ReplyDeletethe food is delicious!............................................................

ReplyDeleteyou‘re so smart!............................................................

ReplyDeleteNice to meet u........................................

ReplyDeleteLearning makes a good man better and ill man worse.............................................................

ReplyDelete成人免費線上看 日本情色視訊 ut聊天網 免費線上色情片 yam交友 女優影片分享 露點 成人免費影片觀看 偷拍貼圖站 美女聊天室 愛情 歐美情趣圖片 女優18禁 台灣絲襪美少女 85cc免費小短片影城 免費a片直撥網 av情色影片 卡通色情影片區 一夜情 影音383 完美女人影片試看 美少女 性美女愛 辣妹強姦 人妻av下載 成人 成人視訊 空姐絲襪 a片a圖論壇 偷拍寫真 85cc 免費影片欣 微風成人區成人寫真 成人嘟嘟網免費看 www.7777th.com 杜雷斯免費貼圖區 援交妹貼圖區 嘟嘟情人色網 dudu 台南鋼管秀 pub 日本av線上 洪爺影片交流區 大大奶的 ab 女傭 sex888 okk 免費下載 巨乳人妻 敏感帶 後宮無碼光碟網 限制級 0204成人影片 無碼性愛影片 走光照

ReplyDelete你不能左右天氣，但你可以改變心情.............................................................

ReplyDelete支持你就對了!． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ．

ReplyDelete河水永遠是相同的，可是每一剎那又都是新的。......................................................................

ReplyDelete河水永遠是相同的，可是每一剎那又都是新的。.................................................................

ReplyDelete人有兩眼一舌，是為了觀察倍於說話的緣故。............................................................

ReplyDelete如果成為一支火柴，也要點亮一個短暫的宇宙；如果是一隻烏鴉，也要叫疼閉塞的耳膜。.................................................................

ReplyDelete好棒的地方 我一定要常來~~~^^~..................................................................

ReplyDelete你文章很棒的~繼續分享給大家~~~~..................................................................

ReplyDeleteBeauty, unaccompanied by virtue, is as a flower without perfume...................................................................

ReplyDelete寂寞又無聊 看到你的BLOG 加油喔!!............................................................

ReplyDelete路過看到好的blog，來留言湊個熱鬧............................................................

ReplyDelete人生中最重要的是要自尊、自愛、自立、自強、自信。..................................................

ReplyDelete喜歡這裡-支持你的更新............................................................

ReplyDelete人若賺得全世界,賠上自己的靈魂,有什麼益處？.......................................................

ReplyDelete喘口氣，看個文章，謝謝您的格子囉~~............................................................

ReplyDelete成熟，就是有能力適應生活中的模糊。............................................................

ReplyDelete人不可以求其備，必捨其所短，取其所長............................................................

ReplyDelete困難的不在於新概念，而在於逃避舊有的概念。......................................................................

ReplyDelete一棵樹除非在春天開了花，否則難望在秋天結果。..................................................

ReplyDelete看看blog調整心情，又要來繼續工作，大家加油............................................................

ReplyDelete請繼續發表好文！加油加油再加油！............................................................

ReplyDelete