{"id":813,"date":"2025-07-30T17:05:49","date_gmt":"2025-07-30T11:35:49","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=813"},"modified":"2025-07-30T17:05:51","modified_gmt":"2025-07-30T11:35:51","slug":"geeks-training","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/geeks-training\/","title":{"rendered":"Geek&#8217;s Training | 2D Dynamic Programming | GFG Practice"},"content":{"rendered":"\n<p>Geek is going for a training program for n days. He can perform any of these activities:&nbsp;<strong>Running<\/strong>,&nbsp;<strong>Fighting<\/strong>, and&nbsp;<strong>Learning&nbsp;<\/strong>Practice. Each activity has some point on each day. As Geek wants to improve all his skills, he can&#8217;t do the same activity on two consecutive days.&nbsp;Given a 2D array&nbsp;<code>arr[][]<\/code>&nbsp;of size n where&nbsp;<code>arr[i][0]<\/code>,&nbsp;<code>arr[i][1]<\/code>, and&nbsp;<code>arr[i][2]<\/code>&nbsp;represent the merit points for&nbsp;<strong>Running<\/strong>,&nbsp;<strong>Fighting<\/strong>, and&nbsp;<strong>Learning<\/strong>&nbsp;on the i-th day, determine the maximum total merit points Geek can achieve .<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/geeks-training\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> arr[]= [[1, 2, 5], [3, 1, 1], [3, 3, 3]]\n<strong>Output: <\/strong>11\n<strong>Explanation: <\/strong>Geek will learn a new move and earn 5 point then on second day he will do running and earn 3 point and on third day he will do fighting and earn 3 points so, maximum merit point will be 11.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> arr[]= [[1, 1, 1], [2, 2, 2], [3, 3, 3]]\n<strong>Output: <\/strong>6\n<strong>Explanation: <\/strong>Geek can perform any activity each day while adhering to the constraints, in order to maximize his total merit points as 6.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> arr[]= [[4, 2, 6]]\n<strong>Output: <\/strong>6\n<strong>Explanation: <\/strong>Geek will learn a new move to make his merit points as 6.<\/pre>\n\n\n\n<p><strong>Constraint:<\/strong><br>1 &lt;=&nbsp; n &lt;= 10<sup>5&nbsp; &nbsp;<\/sup><br>1 &lt;=&nbsp; arr[i][j] &lt;= 100<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-83ac2287-abca-47f6-86fb-74f15a9e37b2\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#0-solution-1-brute-force-approach-pure-recursion\" style=\"\">Solution 1: Brute Force Approach (Pure Recursion)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#5-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#6-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#7-solution-2-memoization-approach-top-down-dp\" style=\"\">Solution 2: Memoization Approach (Top-Down DP)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#8-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#9-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#10-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#11-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#12-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#13-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#14-solution-3-tabulation-approach-bottom-up-dp\" style=\"\">Solution 3: Tabulation Approach (Bottom-Up DP)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#15-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#16-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#17-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#18-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#19-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#20-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#21-solution-4-tabulation-space-optimization-approach-optimal\" style=\"\">Solution 4: Tabulation (Space Optimization) Approach (Optimal)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#22-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#23-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#24-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#25-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#26-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#27-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#28-summary\" style=\"\">Summary<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/geeks-training\/#29-overall-conclusion\" style=\"\">Overall Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-pure-recursion\">Solution 1: Brute Force Approach (Pure Recursion)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think recursively: For each day, try all possible tasks that differ from the last day&#8217;s task, add the points, and recurse to the previous day. At day 0, pick the max possible task != last. This explores all valid paths backward, choosing the maximum at each step.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Base Case: If day == 0, return max of arr[i] where i != last.<\/li>\n\n\n\n<li>Recursive Case: For current day, loop over tasks i (0-2), if i != last, compute arr[day][i] + solve(day-1, i), and take the global max.<\/li>\n\n\n\n<li>&#8216;last&#8217; starts as 3 (no previous constraint).<\/li>\n\n\n\n<li>Explores exponential paths due to overlaps.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, day, last, arr):\n        # Base case: Day 0, pick max task != last\n        if day == 0:\n            maxi = 0\n            for i in range(0, 3):\n                if last != i:\n                    maxi = max(maxi, arr[day][i])\n            return maxi\n        # For current day, try all valid tasks\n        maxi = 0\n        for i in range(0, 3):\n            if last != i:\n                maxi = max(maxi, arr[day][i] + self.solve(day - 1, i, arr))\n        return maxi\n\n    def maximumPoints(self, arr):\n        n = len(arr)\n        # Start from last day with no previous task (last=3)\n        return self.solve(n - 1, 3, arr)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">day<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">last<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: Day 0, pick max task != last<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> day == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> last != i:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, arr[day][i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># For current day, try all valid tasks<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> last != i:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, arr[day][i] + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(day - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, i, arr))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> maxi<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">maximumPoints<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(arr)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Start from last day with no previous task (last=3)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">, arr)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>The&nbsp;<code>solve<\/code>&nbsp;function computes max points from day to 0, given the last task. It loops over possible tasks for the current day (skipping if same as last), recurses with the chosen task as new last, and accumulates max. The main function starts from day n-1 with last=3 (dummy).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise:<\/strong>&nbsp;Time O(3^n) (up to 3 choices per day), Space O(n) (recursion depth).<\/li>\n\n\n\n<li><strong>Simplified:<\/strong>&nbsp;Time exponential O(3^n), slow for large n; Space O(n) from stack.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>Like trying every possible training schedule without remembering past choices, intuitive but repeats a lot of work!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-solution-2-memoization-approach-top-down-dp\">Solution 2: Memoization Approach (Top-Down DP)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-intuition\">Intuition<\/h3>\n\n\n\n<p>Recursion recomputes subproblems (e.g., points from day 5 with last=1 multiple times). Use a DP table [day][last] to store results, checking before computing.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>DP: n x 4 array (last 0-3), init -1.<\/li>\n\n\n\n<li>If dp[day][last] != -1, return it.<\/li>\n\n\n\n<li>Else, compute as recursion, store in dp.<\/li>\n\n\n\n<li>Reduces to linear by caching.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, day, last, arr, dp):\n        # Check memo\n        if dp[day][last] != -1:\n            return dp[day][last]\n        # Base case for day 0\n        if day == 0:\n            maxi = 0\n            for i in range(0, 3):\n                if last != i:\n                    maxi = max(maxi, arr[day][i])\n            return maxi\n        # Compute max for current day\n        maxi = 0\n        for i in range(0, 3):\n            if last != i:\n                maxi = max(maxi, arr[day][i] + self.solve(day - 1, i, arr, dp))\n        # Store in memo\n        dp[day][last] = maxi\n        return dp[day][last]\n\n    def maximumPoints(self, arr):\n        n = len(arr)\n        # DP table: n days x 4 last tasks\n        dp = [[-1 for _ in range(4)] for _ in range(n)]\n        return self.solve(n - 1, 3, arr, dp)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">day<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">last<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">dp<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Check memo<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> dp[day][last] != -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[day][last]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case for day 0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> day == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> last != i:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, arr[day][i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Compute max for current day<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> last != i:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, arr[day][i] + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(day - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, i, arr, dp))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Store in memo<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[day][last] = maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[day][last]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">maximumPoints<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(arr)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># DP table: n days x 4 last tasks<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">, arr, dp)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>Adds dp check\/store to recursion. Computes only once per state (day, last), reusing for efficiency.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise:<\/strong>&nbsp;Time O(n * 4 * 3) = O(n), Space O(n*4) + O(n) stack.<\/li>\n\n\n\n<li><strong>Simplified:<\/strong>&nbsp;Time O(n), Space O(n) (table + stack).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>Now with a notebook for each day and previous choice, look up answers instead of recalculating!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"14-solution-3-tabulation-approach-bottom-up-dp\">Solution 3: Tabulation Approach (Bottom-Up DP)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-intuition\">Intuition<\/h3>\n\n\n\n<p>Build from day 0 upward. For each day and possible last, compute max by trying valid tasks, using previous day&#8217;s dp.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>DP n x 4.<\/li>\n\n\n\n<li>Init day 0: dp[last] = max valid tasks != last (special for last=3: overall max).<\/li>\n\n\n\n<li>For each day 1 to n-1, for each last 0-3, max over i != last: arr[day][i] + dp[day-1][i].<\/li>\n\n\n\n<li>Return dp[n-1].<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def maximumPoints(self, arr):\n        n = len(arr)\n        # DP table: n days x 4 last tasks\n        dp = [[-1 for _ in range(4)] for _ in range(n)]\n        # Init day 0 for each possible last\n        dp[0][0] = max(arr[0][1], arr[0][2])\n        dp[0][1] = max(arr[0][0], arr[0][2])\n        dp[0][2] = max(arr[0][0], arr[0][1])\n        dp[0][3] = max(arr[0][0], arr[0][1], arr[0][2])\n        # Fill for each day\n        for day in range(1, n):\n            for last in range(0, 4):\n                maxi = 0\n                for i in range(0, 3):\n                    if i != last:\n                        maxi = max(maxi, arr[day][i] + dp[day - 1][i])\n                dp[day][last] = maxi\n        return dp[n - 1][3]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">maximumPoints<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(arr)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># DP table: n days x 4 last tasks<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Init day 0 for each possible last<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Fill for each day<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> day <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> last <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i != last:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, arr[day][i] + dp[day - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                dp[day][last] = maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"18-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>Fills dp bottom-up, ensuring each cell uses previous day&#8217;s values. No recursion.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"19-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise:<\/strong>&nbsp;Time O(n * 4 * 3) = O(n), Space O(n*4).<\/li>\n\n\n\n<li><strong>Simplified:<\/strong>&nbsp;Time O(n), Space O(n).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"20-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>Like filling a schedule table day by day, building on yesterday&#8217;s best choices!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"21-solution-4-tabulation-space-optimization-approach-optimal\">Solution 4: Tabulation (Space Optimization) Approach (Optimal)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"22-intuition\">Intuition<\/h3>\n\n\n\n<p>Since we only need previous day&#8217;s dp, use two 1D arrays: prev and curr. Update curr based on prev, then set prev = curr.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"23-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Init prev as day 0 values.<\/li>\n\n\n\n<li>For each day, compute curr similarly.<\/li>\n\n\n\n<li>Copy curr to prev.<\/li>\n\n\n\n<li>O(1) space extra.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"24-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def maximumPoints(self, arr):\n        n = len(arr)\n        # Prev row for space opt\n        prev = [-1 for _ in range(4)]\n        # Init for day 0\n        prev[0] = max(arr[0][1], arr[0][2])\n        prev[1] = max(arr[0][0], arr[0][2])\n        prev[2] = max(arr[0][0], arr[0][1])\n        prev[3] = max(arr[0][0], arr[0][1], arr[0][2])\n        # For each day\n        for day in range(1, n):\n            curr = [-1 for _ in range(4)]\n            for last in range(0, 4):\n                maxi = 0\n                for i in range(0, 3):\n                    if i != last:\n                        maxi = max(maxi, arr[day][i] + prev[i])\n                curr[last] = maxi\n            # Update prev to curr\n            prev = curr.copy()\n        return prev[3]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">maximumPoints<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(arr)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Prev row for space opt<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev = [-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Init for day 0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev[<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev[<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev[<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># For each day<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> day <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            curr = [-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> last <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                maxi = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i != last:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(maxi, arr[day][i] + prev[i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                curr[last] = maxi<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Update prev to curr<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev = curr.copy()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> prev[<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"25-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>Uses prev array for previous day, computes curr, updates. Minimizes space.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"26-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise:<\/strong>&nbsp;Time O(n * 4 * 3) = O(n), Space O(4) = O(1).<\/li>\n\n\n\n<li><strong>Simplified:<\/strong>&nbsp;Time O(n), Space O(1).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"27-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>Like keeping only yesterday&#8217;s notes, efficient and clutter-free!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"28-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Recursion (Brute Force)<\/td><td>O(3^n)<\/td><td>O(n)<\/td><td>Easy<\/td><td>Intuition building<\/td><\/tr><tr><td>Memoization (Top-Down DP)<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Medium<\/td><td>Caching practice<\/td><\/tr><tr><td>Tabulation (Bottom-Up DP)<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Medium<\/td><td>Iterative reliability<\/td><\/tr><tr><td>Space-Optimized Tabulation<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Medium-Hard<\/td><td>Optimal performance<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"29-overall-conclusion\">Overall Conclusion<\/h2>\n\n\n\n<p>The Geek&#8217;s Training problem sharpens your DP state management skills. Start recursive for understanding, optimize with memo\/tabulation, and ace interviews with space efficiency. Practice similar problems on GFG or LeetCode.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Geek is going for a training program for n days. He can perform any of these activities:&nbsp;Running,&nbsp;Fighting, and&nbsp;Learning&nbsp;Practice. Each activity has some point on each day. As Geek wants to improve all his skills, he can&#8217;t do the same activity on two consecutive days.&nbsp;Given a 2D array&nbsp;arr[][]&nbsp;of size n where&nbsp;arr[i][0],&nbsp;arr[i][1], and&nbsp;arr[i][2]&nbsp;represent the merit points for&nbsp;Running,&nbsp;Fighting,<\/p>\n","protected":false},"author":1,"featured_media":814,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[38,19],"class_list":{"0":"post-813","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-dynamic-programming-on-2d-arrays","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/geek-training-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/813","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=813"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/813\/revisions"}],"predecessor-version":[{"id":816,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/813\/revisions\/816"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/814"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=813"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=813"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=813"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}