<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Atalyk Akash on Medium]]></title>
        <description><![CDATA[Stories by Atalyk Akash on Medium]]></description>
        <link>https://medium.com/@aatalyk?source=rss-8d071aa3d711------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*2WQrWKYXHxTSP3N_1lajcw.jpeg</url>
            <title>Stories by Atalyk Akash on Medium</title>
            <link>https://medium.com/@aatalyk?source=rss-8d071aa3d711------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 11:15:49 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@aatalyk/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[How to calculate the time complexity of a recursive function]]></title>
            <link>https://aatalyk.medium.com/how-to-calculate-the-time-complexity-of-a-recursive-function-2cb6437a93ed?source=rss-8d071aa3d711------2</link>
            <guid isPermaLink="false">https://medium.com/p/2cb6437a93ed</guid>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Atalyk Akash]]></dc:creator>
            <pubDate>Sun, 29 Oct 2023 12:42:40 GMT</pubDate>
            <atom:updated>2023-11-17T18:13:17.417Z</atom:updated>
            <content:encoded><![CDATA[<p>To calculate the time-complexity of a recursive function, try to answer the following questions:</p><ul><li>How many times does a function call itself (<em>t</em>)?</li><li>How many times is a function being recursed (<em>k</em>)?</li></ul><p>Based on that, we can say that the time complexity of a plain recursive solution is exponential <strong><em>O(t^k)</em></strong>. If we draw a recursive tree, we can find the time complexity by summing up the number of nodes in the tree.</p><p>Fibonacci Sequence</p><p>To find the <strong><em>nth</em></strong> Fibonacci number, we need to sum up two previous Fibonacci numbers.</p><p><em>F(n) = F(n − 1) + F(n − 2)</em></p><p>The function is being called two times:</p><ul><li>F(n-1)</li><li>F(n-2)</li></ul><p>Then it’s being recursed <em>n</em> times from <em>n</em> to 0, where <em>n</em> is the depth of the recursive tree for the function. So, the time complexity of the plain recursive solution is <em>O(2^n)</em>.</p><p>Let’s calculate the time complexity of the function to see if the statement above is true. Let’s denote <strong><em>T(n)</em></strong> as a function to calculate the time complexity of the Fibonacci Sequence.</p><p><em>T(n) = T(n-1) + T(n-2) + C</em>,</p><p>where<em> T(n − 1)</em> and <em>T(n − 2)</em> are the time complexities to find <strong><em>(n-1)th</em></strong> Fibonacci and <strong><em>(n-2)th</em></strong> Fibonacci numbers respectively, and <em>C</em> is the number of constant operations performed inside the recursive call.</p><p>For simplicity let’s assume that <em>T(n − 2) ≤ T(n − 1)</em>.</p><p><em>T(n) = 2×T(n-1) + C</em></p><p><em>T(n-1) = 2×T(n-2) + C</em></p><p><em>T(n) = 2×(2×T(n-2) + C) + C</em></p><p><em>T(n) = 2^2×T(n-2) + 3C</em></p><p><em>T(n-2) = 2×T(n-3) + C</em></p><p><em>T(n) = 2^2×(2×T(n-3) + C) + 3C</em></p><p><em>T(n) = 2^3×T(n-3) + 7C</em></p><p><em>T(n) = 2^k×T(n-k) + (2^k-1)×C</em></p><p><em>T(0) = 1</em></p><p><em>n-k = 0</em></p><p><em>n = k</em></p><p><em>T(n) = 2^n×T(0) + (2^n-1)×C = 2^n+(2^n-1)×C</em></p><p>The upper bound time complexity is <em>O(2^n)</em>.</p><p>Thank you</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2cb6437a93ed" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How I wrote my first programming ebook]]></title>
            <link>https://blog.devgenius.io/how-i-wrote-my-first-programming-ebook-3b2c183f6150?source=rss-8d071aa3d711------2</link>
            <guid isPermaLink="false">https://medium.com/p/3b2c183f6150</guid>
            <category><![CDATA[ebook-pdf]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[programming-books]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <dc:creator><![CDATA[Atalyk Akash]]></dc:creator>
            <pubDate>Wed, 12 May 2021 15:36:53 GMT</pubDate>
            <atom:updated>2021-05-17T20:33:56.093Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Su_uqZVJh8_DufNEo8wVTA.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@glenncarstenspeters?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Glenn Carstens-Peters</a> on <a href="https://unsplash.com/s/photos/write?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>Recently, I have finished my first ebook <a href="https://gumroad.com/l/cAEgH">Dynamic Programming Guide</a>. Today, I would like to share my story of writing this guide.</p><p>It was 2019 when I decided to rewind my preparation for coding interviews. I started with solving LeetCode problems without studying new topics. My aim was to land at Google, so I expected to feel comfortable with medium and hard-level problems. And of course, Dynamic Programming is one of the favorite questions at Google interviews, and it was a nightmare for me. I remember that I tried so hard to understand DP at university. Still, I could only understand that DP is about remembering previous decisions and nothing more. During my interview preparation, I always tried to avoid DP, skipping it, or hoping that I wouldn’t meet DP in my interviews. But this strategy cost me confidence. I always felt like I wasn’t ready for an interview cause I didn’t cover all of the topics.</p><p>One day, I realized that the strategy I chose wasn’t the path that would lead to success. That’s how I started my DP journey. I started looking for tutorials, videos, or articles on DP. Even though there are many resources available online, it’s not easy to find a systematic approach to understand the topic. Some videos explain what DP is, top-down or bottom-up solution. Some articles explain how to solve problems recursively, for example, solutions of widely known DP problems. I looked for a way to combine all of these resources. After watching some videos and reading blog posts, I steadily started solving easy DP problems, most of the time spending my time looking at solutions. To make the learning easier, I started looking for patterns in problems to classify them into categories. This way, I wanted to clarify what to expect from a problem regarding constraints and possible solutions, such as expecting quadratic time complexity for DP problems on strings or summing up possible ways for combinatorial problems. I spent two months classifying all LeetCode problems on DP that I solved into categories. That’s how I came up with an idea to write <a href="https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns">Dynamic Programming Patterns</a>. I created a markdown file and started to write little by little every day. In two months, I came up with six patterns.</p><figure><img alt="Picture from 2019" src="https://cdn-images-1.medium.com/max/575/1*yiMrZuJFoZexekk06222UQ.jpeg" /><figcaption>Picture from 2019</figcaption></figure><p>In December, LeetCode announced the contest for the best post of 2019, and I decided to upload my work there. I didn’t expect it would make a significant impact cause even though I found the patterns useful for me, it was still my opinion.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ipI2zF7ISMuro-6t02V2ZA.png" /></figure><p>Surprisingly, the post got viral, and in the first two days, it hit 894 upvotes and 10k views. Upvotes kept growing every day, and at the end of December, my post was chosen as one of the best posts of 2019. I received fantastic giveaways from LeetCode.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5WTKjkSf1koCrdb1GZogqA.jpeg" /></figure><p>Currently, on average, the post gets five upvotes in a day. At the moment of writing this post, Dynamic Programming Patterns was upvoted 6.9k times and viewed 358k times (the most upvoted post in LeetCode). I received a lot of feedback. Sometimes people stated that it’s useless to study patterns if you do not understand the general idea. To some extent, I agree with the fact that it’s always better to build fundamentals first. This motivated me to create a video series on DP. At that time, I have already had a YouTube channel where I upload programming videos. In the next few days, I recorded my first video explaining the concept of Dynamic Programming. I should say that making a video in one shot wasn’t easy. I thought the reason was the fact that I didn’t have lecture notes to follow while recording a video. So I decided first to write down my lecture notes and then record videos. I decided to keep my lecture notes in a markdown file.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FI-s72xIFsC4%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DI-s72xIFsC4&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FI-s72xIFsC4%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/ebb4ce01b4e13f2b988f8e6f89d08601/href">https://medium.com/media/ebb4ce01b4e13f2b988f8e6f89d08601/href</a></iframe><p>I read the paper by Richard Bellman on Dynamic Programming to understand the theory of DP. The paper gave an idea of DP, such as what problems the DP aims to solve and how to use state variables for memoization. I wanted to make it easy to understand how to solve DP problems; thus, I divided the problem solving into steps that one could follow. After finishing writing the explanation for the top-down solution, the next move was to explain the bottom-up solution. Similar to the top-down solution, I broke the bottom-up solution into several steps. After every explanation, I added solutions for problems such as the Fibonacci Sequence following that steps. The next move was to write the analysis of time and space complexities. In the next couple of months, the first draft of my lecture notes was ready. Even though lecture notes were prepared, I changed my mind about creating video series. Instead, I decided to convert lecture notes into an ebook. I sent the first draft to my friends and received many suggestions to change particular topics inside the ebook. Considering all suggestions, I changed some of the topics inside the ebook and removed some unnecessary parts. After that, I sent an updated version to my friends, but this time, I got few suggestions, and they admit that the ebook looked good overall. I changed few places and add a cover made in Canva. The last part was to proofread it and sent it to Gumroad. I couldn’t decide initially where to upload the ebook to Gumroad or Amazon KDP. But later, I stopped on Gumroad.</p><p>To sum up, this was my first experience of writing something bigger than an article. I hope I will keep this pace and write more books about programming. You’re probably feeling curious where I get an offer from FAANG or not, but it’s a different story.</p><p>Thank you for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3b2c183f6150" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/how-i-wrote-my-first-programming-ebook-3b2c183f6150">How I wrote my first programming ebook</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[When I typed aatalyk in Google]]></title>
            <link>https://aatalyk.medium.com/when-i-typed-aatalyk-in-google-e29b0b0d9421?source=rss-8d071aa3d711------2</link>
            <guid isPermaLink="false">https://medium.com/p/e29b0b0d9421</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[patterns]]></category>
            <category><![CDATA[interview-preparation]]></category>
            <dc:creator><![CDATA[Atalyk Akash]]></dc:creator>
            <pubDate>Sat, 10 Apr 2021 14:13:28 GMT</pubDate>
            <atom:updated>2021-04-10T14:13:28.986Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/661/1*VIo-hwudy76EbpX0unKaDw.png" /></figure><p>👉🏼 <a href="https://aatalyk.medium.com/dynamic-programming-patterns-595815f2468d?source=your_stories_page-------------------------------------">Dynamic Programming Patterns</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e29b0b0d9421" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dynamic Programming Patterns]]></title>
            <link>https://medium.com/dynamic-programming-patterns/dynamic-programming-patterns-595815f2468d?source=rss-8d071aa3d711------2</link>
            <guid isPermaLink="false">https://medium.com/p/595815f2468d</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[pattern-recognition]]></category>
            <dc:creator><![CDATA[Atalyk Akash]]></dc:creator>
            <pubDate>Fri, 09 Apr 2021 13:05:55 GMT</pubDate>
            <atom:updated>2021-08-28T20:42:46.209Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UlNP1-CgFsB_Vqb720Pb6w.png" /></figure><p>Before starting the topic let me introduce myself. I am a Mobile Developer currently working in Warsaw and spending my free time on interview preparations. I started to prepare for interviews two years ago. At that time I should say I could not solve the two sum problem. Easy problems seemed to me like hard ones so most of the time I had to look at editorials and discuss sections. Currently, I have solved ~800 problems and time to time participate in contests. I usually solve 3 problems in a contest and sometimes 4 problems. Ok, let’s come back to the topic.</p><p>Recently I have concentrated my attention on Dynamic Programming cause its one of the hardest topics in an interview prep. After solving ~140 problems in DP I have noticed that there are few patterns that can be found in different problems. So I did research on that and find the following topics. I will not give complete ways how to solve problems but these patterns may be helpful in solving DP.</p><p><strong>If you are looking for beginner guide for Dynamic Programming check out </strong><a href="https://aatalyk.gumroad.com/l/cAEgH"><strong>Dynamic Programming Guide</strong></a><strong>.</strong></p><h3>Patterns</h3><h3>Minimum (Maximum) Path to Reach a Target</h3><h4>Statement</h4><blockquote><em>Given a target find minimum (maximum) cost / path / sum to reach the target.</em></blockquote><h4>Approach</h4><blockquote><em>Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.</em></blockquote><pre>routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]</pre><p>Generate optimal solutions for all values in the target and return the value for the target.</p><h4>Top-Down</h4><pre>for (int j = 0; j &lt; ways.size(); ++j) {<br>    result = min(result, topDown(target - ways[j]) + cost/ path / sum);<br>}</pre><pre>return memo[/*state parameters*/] = result;</pre><h4>Bottom-Up</h4><pre>for (int i = 1; i &lt;= target; ++i) {<br>   for (int j = 0; j &lt; ways.size(); ++j) {<br>       if (ways[j] &lt;= i) {<br>           dp[i] = min(dp[j], dp[i - ways[j]] + cost / path / sum);<br>       }<br>   }<br>}<br> <br>return dp[target];</pre><h4>Similar Problems</h4><p><a href="https://leetcode.com/problems/min-cost-climbing-stairs/">746. Min Cost Climbing Stairs</a> Easy</p><h4>Top-Down</h4><pre>int result = min(minCost(n-1, cost, memo), minCost(n-2, cost, memo)) + (n == cost.size() ? 0 : cost[n]);</pre><pre>return memo[n] = result;</pre><h4>Bottom-Up</h4><pre>for (int i = 2; i &lt;= n; ++i) {<br>   dp[i] = min(dp[i-1], dp[i-2]) + (i == n ? 0 : cost[i]);<br>}<br> <br>return dp[n]</pre><p><a href="https://leetcode.com/problems/minimum-path-sum/">64. Minimum Path Sum</a> Medium</p><h4>Top-Down</h4><pre>int result = min(pathSum(i+1, j, grid, memo), pathSum(i, j+1, grid, memo)) + grid[i][j];<br>    <br>return memo[i][j] = result;</pre><h4>Bottom-Up</h4><pre>for (int i = 1; i &lt; n; ++i) {<br>   for (int j = 1; j &lt; m; ++j) {<br>       grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];<br>   }<br>}<br> <br>return grid[n-1][m-1]</pre><p><a href="https://leetcode.com/problems/coin-change/">322. Coin Change</a> Medium</p><h4>Top-Down</h4><pre>for (int i = 0; i &lt; coins.size(); ++i) {<br>    if (coins[i] &lt;= target) { // check validity of a sub-problem<br>        result = min(ans, CoinChange(target - coins[i], coins) + 1);<br>    }<br>}</pre><pre>return memo[target] = result;</pre><h4>Bottom-Up</h4><pre>for (int j = 1; j &lt;= amount; ++j) {<br>   for (int i = 0; i &lt; coins.size(); ++i) {<br>       if (coins[i] &lt;= j) {<br>           dp[j] = min(dp[j], dp[j - coins[i]] + 1);<br>       }<br>   }<br>}</pre><pre>return dp[amount];</pre><p><a href="https://leetcode.com/problems/minimum-falling-path-sum/">931. Minimum Falling Path Sum</a> Medium</p><p><a href="https://leetcode.com/problems/minimum-cost-for-tickets/">983. Minimum Cost For Tickets</a> Medium</p><p><a href="https://leetcode.com/problems/2-keys-keyboard/">650. 2 Keys Keyboard</a> Medium</p><p><a href="https://leetcode.com/problems/perfect-squares/">279. Perfect Squares</a> Medium</p><p><a href="https://leetcode.com/problems/last-stone-weight-ii/">1049. Last Stone Weight II</a> Medium</p><p><a href="https://leetcode.com/problems/triangle/">120. Triangle</a> Medium</p><p><a href="https://leetcode.com/problems/ones-and-zeroes/">474. Ones and Zeroes</a> Medium</p><p><a href="https://leetcode.com/problems/maximal-square/">221. Maximal Square</a> Medium</p><p><a href="https://leetcode.com/problems/coin-change/">322. Coin Change</a> Medium</p><p><a href="https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/">1240. Tiling a Rectangle with the Fewest Squares</a> Hard</p><p><a href="https://leetcode.com/problems/dungeon-game/">174. Dungeon Game</a> Hard</p><p><a href="https://leetcode.com/problems/minimum-number-of-refueling-stops/">871. Minimum Number of Refueling Stops</a> Hard</p><h3>Distinct Ways</h3><h4>Statement</h4><blockquote><em>Given a target find a number of distinct ways to reach the target.</em></blockquote><h4>Approach</h4><blockquote><em>Sum all possible ways to reach the current state.</em></blockquote><pre>routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]</pre><p>Generate sum for all values in the target and return the value for the target.</p><h4>Top-Down</h4><pre>for (int j = 0; j &lt; ways.size(); ++j) {<br>    result += topDown(target - ways[j]);<br>}</pre><pre>return memo[/*state parameters*/] = result;</pre><h4>Bottom-Up</h4><pre>for (int i = 1; i &lt;= target; ++i) {<br>   for (int j = 0; j &lt; ways.size(); ++j) {<br>       if (ways[j] &lt;= i) {<br>           dp[j] += dp[i - ways[j]];<br>       }<br>   }<br>}<br> <br>return dp[target]</pre><h4>Similar Problems</h4><p><a href="https://leetcode.com/problems/climbing-stairs/">70. Climbing Stairs</a> Easy</p><h4>Top-Down</h4><pre>int result = climbStairs(n-1, memo) + climbStairs(n-2, memo); <br>    <br>return memo[n] = result;</pre><h4>Bottom-Up</h4><pre>for (int stair = 2; stair &lt;= n; ++stair) {<br>   for (int step = 1; step &lt;= 2; ++step) {<br>       dp[stair] += dp[stair-step];   <br>   }<br>}</pre><pre>return dp[n];</pre><p><a href="https://leetcode.com/problems/unique-paths/">62. Unique Paths</a> Medium</p><h4>Top-Down</h4><pre>int result = UniquePaths(x-1, y) + UniquePaths(x, y-1);</pre><pre>return memo[x][y] = result;</pre><h4>Bottom-Up</h4><pre>for (int i = 1; i &lt; m; ++i) {<br>   for (int j = 1; j &lt; n; ++j) {<br>       dp[i][j] = dp[i][j-1] + dp[i-1][j];<br>   }<br>}</pre><p><a href="https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/">1155. Number of Dice Rolls With Target Sum</a> Medium</p><p><a href="https://leetcode.com/problems/knight-probability-in-chessboard/">688. Knight Probability in Chessboard</a> Medium</p><p><a href="https://leetcode.com/problems/target-sum/">494. Target Sum</a> Medium</p><p><a href="https://leetcode.com/problems/combination-sum-iv/">377. Combination Sum IV</a> Medium</p><p><a href="https://leetcode.com/problems/knight-dialer/">935. Knight Dialer</a> Medium</p><p><a href="https://leetcode.com/problems/dice-roll-simulation/">1223. Dice Roll Simulation</a> Medium</p><p><a href="https://leetcode.com/problems/partition-equal-subset-sum/">416. Partition Equal Subset Sum</a> Medium</p><p><a href="https://leetcode.com/problems/soup-servings/">808. Soup Servings</a> Medium</p><p><a href="https://leetcode.com/problems/domino-and-tromino-tiling/">790. Domino and Tromino Tiling</a> Medium</p><p><a href="https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/">801. Minimum Swaps To Make Sequences Increasing</a></p><p><a href="https://leetcode.com/problems/number-of-longest-increasing-subsequence/">673. Number of Longest Increasing Subsequence</a> Medium</p><p><a href="https://leetcode.com/problems/unique-paths-ii/">63. Unique Paths II</a> Medium</p><p><a href="https://leetcode.com/problems/out-of-boundary-paths/">576. Out of Boundary Paths</a> Medium</p><p><a href="https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/">1269. Number of Ways to Stay in the Same Place After Some Steps</a> Hard</p><p><a href="https://leetcode.com/problems/count-vowels-permutation/">1220. Count Vowels Permutation</a> Hard</p><h3>Merging Intervals</h3><h4>Statement</h4><blockquote><em>Given a set of numbers find an optimal solution for a problem considering the current number and the best you can get from the left and right sides.</em></blockquote><h4>Approach</h4><blockquote><em>Find all optimal solutions for every interval and return the best possible answer.</em></blockquote><pre>// from i to j<br>dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]</pre><p>Get the best from the left and right sides and add a solution for the current position.</p><h4>Top-Down</h4><pre>for (int k = i; k &lt;= j; ++k) {<br>    result = max(result, topDown(nums, i, k-1) + result[k] + topDown(nums, k+1, j));<br>}</pre><pre>return memo[/*state parameters*/] = result;</pre><h4>Bottom-Up</h4><pre>for(int l = 1; l&lt;n; l++) {<br>   for(int i = 0; i&lt;n-l; i++) {<br>       int j = i+l;<br>       for(int k = i; k&lt;j; k++) {<br>           dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]);<br>       }<br>   }<br>}<br> <br>return dp[0][n-1]</pre><h4>Similar Problems</h4><p><a href="https://leetcode.com/problems/burst-balloons/">312. Burst Balloons</a> Hard</p><h4>Top-Down</h4><pre>for (int k = i; k &lt;= j; ++k) {<br>    result = max(result, topDown(nums, i, k-1, memo) + (i-1 &gt;= 0 ? nums[i-1] : 1) * nums[k] * (j+1 &lt; nums.size() ? nums[j+1] : 1) + topDown(nums, k+1, j, memo));<br>}</pre><pre>return memo[i][j] = result;</pre><h4>Bottom-Up</h4><pre>for(int l = 1; l &lt; n; l++) {<br>    for(int i = 0; i &lt; n-l; i++) {<br>        int j = i+l;<br>        for(int k = i; k &lt;= j; k++) {<br>            dp[i][j] = max(dp[i][j], (((k&gt;i &amp;&amp; k&gt;0) ? dp[i][k-1] : 0) + (i&gt;0 ? nums[i-1] : 1) * nums[k] * (j&lt;n-1 ? nums[j+1] : 1) + ((k&lt;j &amp;&amp; k&lt;n-1) ? dp[k+1][j] : 0)));<br>        }<br>    }<br>}</pre><pre>return dp[0][n-1];</pre><p><a href="https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/">1130. Minimum Cost Tree From Leaf Values</a> Medium</p><p><a href="https://leetcode.com/problems/unique-binary-search-trees/">96. Unique Binary Search Trees</a> Medium</p><p><a href="https://leetcode.com/problems/minimum-score-triangulation-of-polygon/">1039. Minimum Score Triangulation of Polygon</a> Medium</p><p><a href="https://leetcode.com/problems/remove-boxes/">546. Remove Boxes</a> Medium</p><p><a href="https://leetcode.com/problems/minimum-cost-to-merge-stones/">1000. Minimum Cost to Merge Stones</a> Medium</p><p><a href="https://leetcode.com/problems/guess-number-higher-or-lower-ii/">375. Guess Number Higher or Lower II</a> Medium</p><h3>Dynamic Programming on Strings</h3><p>General problem statement for this pattern can vary but most of the time you are given two strings where the lengths of those strings are not big</p><h4>Statement</h4><blockquote><em>Given two strings </em><em>s1 and </em><em>s2, return </em><em>some result.</em></blockquote><h4>Approach</h4><blockquote><em>Most of the problems on this pattern requires a solution that can be accepted in O(n²) complexity.</em></blockquote><h4>Top-Down</h4><pre>if (s1[i] == s2[j]) {<br>    result = max(result, topDown(s1, s2, i+1, j+1) + 1);<br>}<br>result = max({result, topDown(s1, s2, i+1, j), topDown(s1, s2,<br>i, j+1)});</pre><h4>Bottom-Up</h4><pre>// i - indexing string s1<br>// j - indexing string s2<br>for (int i = 1; i &lt;= n; ++i) {<br>   for (int j = 1; j &lt;= m; ++j) {<br>       if (s1[i-1] == s2[j-1]) {<br>           dp[i][j] = /*code*/;<br>       } else {<br>           dp[i][j] = /*code*/;<br>       }<br>   }<br>}</pre><blockquote><em>If you are given one string </em><em>s the approach may little vary</em></blockquote><pre>for (int l = 1; l &lt; n; ++l) {<br>   for (int i = 0; i &lt; n-l; ++i) {<br>       int j = i + l;<br>       if (s[i] == s[j]) {<br>           dp[i][j] = /*code*/;<br>       } else {<br>           dp[i][j] = /*code*/;<br>       }<br>   }<br>}</pre><p><a href="https://leetcode.com/problems/longest-common-subsequence/">1143. Longest Common Subsequence</a> Medium</p><h4>Top-Down</h4><pre>if (text1[i] == text2[j]) {<br>    result = max(result, topDown(text1, text2, i+1, j+1, memo) + 1);<br>}<br>result = max({result, topDown(text1, text2, i+1, j, memo), topDown(text1, text2, i, j+1, memo)});</pre><pre>return memo[i][j] = result;</pre><h4>Bottom-Up</h4><pre>for (int i = 1; i &lt;= n; ++i) {<br>   for (int j = 1; j &lt;= m; ++j) {<br>       if (text1[i-1] == text2[j-1]) {<br>           dp[i][j] = dp[i-1][j-1] + 1;<br>       } <br>       dp[i][j] = max(dp[i-1][j], dp[i][j-1]);<br>   }<br>}</pre><pre>return dp[n][m];</pre><p><a href="https://leetcode.com/problems/palindromic-substrings/">647. Palindromic Substrings</a> Medium</p><p><a href="https://leetcode.com/problems/longest-palindromic-subsequence/">516. Longest Palindromic Subsequence</a> Medium</p><p><a href="https://leetcode.com/problems/shortest-common-supersequence/">1092. Shortest Common Supersequence</a> Medium</p><p><a href="https://leetcode.com/problems/edit-distance/">72. Edit Distance</a> Hard</p><p><a href="https://leetcode.com/problems/distinct-subsequences/">115. Distinct Subsequences</a> Hard</p><p><a href="https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/">712. Minimum ASCII Delete Sum for Two Strings</a> Medium</p><p><a href="https://leetcode.com/problems/longest-palindromic-substring/">5. Longest Palindromic Substring</a> Medium</p><h3>Decision Making</h3><p>The general problem statement for this pattern is forgiven situation decides whether to use or not to use the current state. So, the problem requires you to make a decision in a current state.</p><h4>Statement</h4><blockquote><em>Given a set of values find an answer with an option to choose or ignore the current value.</em></blockquote><h4>Approach</h4><blockquote><em>If you decide to choose the current value use the previous result where the value was ignored; vice-versa, if you decide to ignore the current value use previous result where value was used.</em></blockquote><h4>Top-Down</h4><pre>if (j &lt; k) {<br>    result = topDown(nums, i+1, j+1, k) + nums[i]; // use the option<br>}<br>result = max(result, topDown(nums, i+1, 0, k)); // ignore the option</pre><h4>Bottom-Up</h4><pre>// i - indexing a set of values<br>// j - options to ignore j values<br>for (int i = 1; i &lt; n; ++i) {<br>   for (int j = 1; j &lt;= k; ++j) {<br>       dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});<br>       dp[i][j-1] = max({dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i]});<br>   }<br>}</pre><p><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/">714. Best Time to Buy and Sell Stock with Transaction Fee</a> Medium</p><h4>Top-Down</h4><pre>if (canSell) {<br>    sell = maxProfit(prices, i+1, false, fee) + prices[i] - fee;<br>}</pre><pre>int skip = maxProfit(prices, i+1, canSell, fee);<br>int buy = maxProfit(prices, i+1, true, fee) - prices[i];</pre><pre>return memo[i][canSell] = max({buy, sell, skip});</pre><h4>Bottom-Up</h4><pre>dp[0][0] = -prices[0];<br>dp[0][1] = 0;</pre><pre>for (int i = 1; i &lt; prices.size(); ++i) {<br>    dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);<br>    dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);<br>}</pre><pre>return dp[n-1][1];</pre><p><a href="https://leetcode.com/problems/house-robber/">198. House Robber</a> Easy</p><p><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock/">121. Best Time to Buy and Sell Stock</a> Easy</p><p><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/">309. Best Time to Buy and Sell Stock with Cooldown</a> Medium</p><p><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/">123. Best Time to Buy and Sell Stock III</a> Hard</p><p><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/">188. Best Time to Buy and Sell Stock IV</a> Hard</p><p>I hope these tips will be helpful 😊</p><p>Follow me for more updates on <a href="https://twitter.com/aatalyk">Twitter</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=595815f2468d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dynamic-programming-patterns/dynamic-programming-patterns-595815f2468d">Dynamic Programming Patterns</a> was originally published in <a href="https://medium.com/dynamic-programming-patterns">Dynamic Programming Patterns</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>