"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});vari=o(85893),t=o(11151);constr={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:newDate("2023-08-17T00:00:00.000Z")}},s=void0,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}];functionc(e){constn={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\n9564\n174782\n18358710\n204824765\n19123334\n882777376367\n99654286167092\n414126568340807033\n41487233473237169429\n5371446525439152975114\n7011332877731778396
