blog/assets/js/9b91a88c.5373e017.js

"use strict";(self.webpackChunkfi=self.webpackChunkfi||[]).push([[2545],{19466:(e,n,o)=>{o.r(n),o.d(n,{assets:()=>l,contentTitle:()=>s,default:()=>m,frontMatter:()=>r,metadata:()=>a,toc:()=>d});var i=o(85893),t=o(11151);const r={id:"pyramid-slide-down",slug:"/recursion/pyramid-slide-down",title:"Introduction to dynamic programming",description:"Solving a problem in different ways.\n",tags:["java","recursion","exponential","greedy","dynamic-programming","top-down-dp","bottom-up-dp"],last_update:{date:new Date("2023-08-17T00:00:00.000Z")}},s=void 0,a={id:"recursion/2023-08-17-pyramid-slide-down/pyramid-slide-down",title:"Introduction to dynamic programming",description:"Solving a problem in different ways.\n",source:"@site/algorithms/04-recursion/2023-08-17-pyramid-slide-down/index.md",sourceDirName:"04-recursion/2023-08-17-pyramid-slide-down",slug:"/recursion/pyramid-slide-down",permalink:"/algorithms/recursion/pyramid-slide-down",draft:!1,unlisted:!1,editUrl:"https://github.com/mfocko/blog/tree/main/algorithms/04-recursion/2023-08-17-pyramid-slide-down/index.md",tags:[{label:"java",permalink:"/algorithms/tags/java"},{label:"recursion",permalink:"/algorithms/tags/recursion"},{label:"exponential",permalink:"/algorithms/tags/exponential"},{label:"greedy",permalink:"/algorithms/tags/greedy"},{label:"dynamic-programming",permalink:"/algorithms/tags/dynamic-programming"},{label:"top-down-dp",permalink:"/algorithms/tags/top-down-dp"},{label:"bottom-up-dp",permalink:"/algorithms/tags/bottom-up-dp"}],version:"current",lastUpdatedAt:1692230400,formattedLastUpdatedAt:"Aug 17, 2023",frontMatter:{id:"pyramid-slide-down",slug:"/recursion/pyramid-slide-down",title:"Introduction to dynamic programming",description:"Solving a problem in different ways.\n",tags:["java","recursion","exponential","greedy","dynamic-programming","top-down-dp","bottom-up-dp"],last_update:{date:"2023-08-17T00:00:00.000Z"}},sidebar:"autogeneratedBar",previous:{title:"Solution to the problem",permalink:"/algorithms/recursion/karel/solution"},next:{title:"Na\xefve solution",permalink:"/algorithms/recursion/pyramid-slide-down/naive"}},l={},d=[{value:"Problem",id:"problem",level:2},{value:"Solving the problem",id:"solving-the-problem",level:2}];function c(e){const n={a:"a",admonition:"admonition",code:"code",em:"em",h2:"h2",li:"li",ol:"ol",p:"p",pre:"pre",section:"section",sup:"sup",...(0,t.a)(),...e.components};return(0,i.jsxs)(i.Fragment,{children:[(0,i.jsx)(n.p,{children:"In this series we will try to solve one problem in different ways."}),"\n",(0,i.jsx)(n.h2,{id:"problem",children:"Problem"}),"\n",(0,i.jsxs)(n.p,{children:["The problem we are going to solve is one of ",(0,i.jsx)(n.em,{children:"CodeWars"})," katas and is called\n",(0,i.jsx)(n.a,{href:"https://www.codewars.com/kata/551f23362ff852e2ab000037",children:"Pyramid Slide Down"}),"."]}),"\n",(0,i.jsxs)(n.p,{children:["We are given a 2D array of integers and we are to find the ",(0,i.jsx)(n.em,{children:"slide down"}),".\n",(0,i.jsx)(n.em,{children:"Slide down"})," is a maximum sum of consecutive numbers from the top to the bottom."]}),"\n",(0,i.jsx)(n.p,{children:"Let's have a look at few examples. Consider the following pyramid:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{children:"   3\n  7 4\n 2 4 6\n8 5 9 3\n"})}),"\n",(0,i.jsx)(n.p,{children:"This pyramid has following slide down:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{children:"   *3\n  *7 4\n 2 *4 6\n8 5 *9 3\n"})}),"\n",(0,i.jsxs)(n.p,{children:["And its value is ",(0,i.jsx)(n.code,{children:"23"}),"."]}),"\n",(0,i.jsxs)(n.p,{children:["We can also have a look at a ",(0,i.jsx)(n.em,{children:"bigger"})," example:"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{children:"                75\n               95 64\n              17 47 82\n             18 35 87 10\n            20  4 82 47 65\n            19  1 23  3 34\n         88  2 77 73  7 63 67\n        99 65  4 28  6 16 70 92\n       41 41 26 56 83 40 80 70 33\n      41 48 72 33 47 32 37 16 94 29\n     53 71 44 65 25 43 91 52 97 51 14\n    70 11 33 28 77 73 17 78 39 68 17 57\n   91 71 52 38 17 14 91 43 58 50 27 29 48\n 63 66  4 68 89 53 67 30 73 16 69 87 40 31\n 4 62 98 27 23 9 70 98 73 93 38 53 60  4 23\n"})}),"\n",(0,i.jsxs)(n.p,{children:["Slide down in this case is equal to ",(0,i.jsx)(n.code,{children:"1074"}),"."]}),"\n",(0,i.jsx)(n.h2,{id:"solving-the-problem",children:"Solving the problem"}),"\n",(0,i.jsx)(n.admonition,{title:"caution",type:"warning",children:(0,i.jsxs)(n.p,{children:["I will describe the following ways you can approach this problem and implement\nthem in ",(0,i.jsx)(n.em,{children:"Java"}),(0,i.jsx)(n.sup,{children:(0,i.jsx)(n.a,{href:"#user-content-fn-1",id:"user-content-fnref-1","data-footnote-ref":!0,"aria-describedby":"footnote-label",children:"1"})}),"."]})}),"\n",(0,i.jsxs)(n.p,{children:["For all of the following solutions I will be using basic ",(0,i.jsx)(n.code,{children:"main"})," function that\nwill output ",(0,i.jsx)(n.code,{children:"true"}),"/",(0,i.jsx)(n.code,{children:"false"})," based on the expected output of our algorithm. Any\nother differences will lie only in the solutions of the problem. You can see the\n",(0,i.jsx)(n.code,{children:"main"})," here:"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-java",children:'public static void main(String[] args) {\n    System.out.print("Test #1: ");\n    System.out.println(longestSlideDown(new int[][] {\n            { 3 },\n            { 7, 4 },\n            { 2, 4, 6 },\n            { 8, 5, 9, 3 }\n    }) == 23 ? "passed" : "failed");\n\n    System.out.print("Test #2: ");\n    System.out.println(longestSlideDown(new int[][] {\n            { 75 },\n            { 95, 64 },\n            { 17, 47, 82 },\n            { 18, 35, 87, 10 },\n            { 20, 4, 82, 47, 65 },\n            { 19, 1, 23, 75, 3, 34 },\n            { 88, 2, 77, 73, 7, 63, 67 },\n            { 99, 65, 4, 28, 6, 16, 70, 92 },\n            { 41, 41, 26, 56, 83, 40, 80, 70, 33 },\n            { 41, 48, 72, 33, 47, 32, 37, 16, 94, 29 },\n            { 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14 },\n            { 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57 },\n            { 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48 },\n            { 63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31 },\n            { 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23 },\n    }) == 1074 ? "passed" : "failed");\n}\n'})}),"\n",(0,i.jsxs)(n.section,{"data-footnotes":!0,className:"footnotes",children:[(0,i.jsx)(n.h2,{className:"sr-only",id:"footnote-label",children:"Footnotes"}),"\n",(0,i.jsxs)(n.ol,{children:["\n",(0,i.jsxs)(n.li,{id:"user-content-fn-1",children:["\n",(0,i.jsxs)(n.p,{children:["cause why not, right!? ",(0,i.jsx)(n.a,{href:"#user-content-fnref-1","data-footnote-backref":"","aria-label":"Back to reference 1",className:"data-footnote-backref",children:"\u21a9"})]}),"\n"]}),"\n"]}),"\n"]})]})}function m(e={}){const{wrapper:n}={...(0,t.a)(),...e.components};return n?(0,i.jsx)(n,{...e,children:(0,i.jsx)(c,{...e})}):c(e)}},11151:(e,n,o)=>{o.d(n,{Z:()=>a,a:()=>s});var i=o(67294);const t={},r=i.createContext(t);function s(e){const n=i.useContext(r);return i.useMemo((function(){return"function"==typeof e?e(n):{...n,...e}}),[n,e])}function a(e){let n;return n=e.disableParentContext?"function"==typeof e.components?e.components(t):e.components||t:s(e.components),i.createElement(r.Provider,{value:n},e.children)}}}]);