d77fe9c2.9c676afc.js

(window.webpackJsonp=window.webpackJsonp||[]).push([[62],{135:function(e,t,n){"use strict";n.r(t),n.d(t,"frontMatter",(function(){return o})),n.d(t,"metadata",(function(){return c})),n.d(t,"toc",(function(){return u})),n.d(t,"default",(function(){return s}));var r=n(147),i=n(149),a=(n(0),n(148)),o={id:"intro",title:"Coordinate-based Dynamic Programming",sidebar_label:"Introduction"},c={unversionedId:"Patterns/DynamicProgramming/Coordinate/intro",id:"Patterns/DynamicProgramming/Coordinate/intro",isDocsHomePage:!1,title:"Coordinate-based Dynamic Programming",description:"Introduction",source:"@site/docs/Patterns/DynamicProgramming/Coordinate/Introduction.md",slug:"/Patterns/DynamicProgramming/Coordinate/intro",permalink:"/docs/Patterns/DynamicProgramming/Coordinate/intro",version:"current",sidebar_label:"Introduction",sidebar:"Patterns",previous:{title:"Confusing Number",permalink:"/docs/Patterns/Backtracking/ConfusingNumber"},next:{title:"Array Questions",permalink:"/docs/Patterns/DynamicProgramming/Coordinate/Array/index"}},u=[{value:"Introduction",id:"introduction",children:[]},{value:"Traits",id:"traits",children:[]}],l={toc:u};function s(e){var t=e.components,o=Object(i.a)(e,["components"]);return Object(a.b)("wrapper",Object(r.a)({},l,o,{components:t,mdxType:"MDXLayout"}),Object(a.b)("p",null,Object(a.b)("img",{src:n(332).default})),Object(a.b)("h2",{id:"introduction"},"Introduction"),Object(a.b)("p",null,"Coordinate-based Dynamic Programming are associated with the coordinates on a array or matrix. You are usually given an array/sequence or a matrix/grid as the input, and the question asks you to find either a subarray, subsequence, vector or path that satisfies a set of conditions. This is one of easier type of Dynamic Programming because it is intuitive to understand."),Object(a.b)("h2",{id:"traits"},"Traits"),Object(a.b)("ul",null,Object(a.b)("li",{parentName:"ul"},"Usually given an array/sequence or grid/matrix as your input"),Object(a.b)("li",{parentName:"ul"},"Need to find a subsequence/vector/path for",Object(a.b)("ul",{parentName:"li"},Object(a.b)("li",{parentName:"ul"},"maximizing/minimizing a certain property"),Object(a.b)("li",{parentName:"ul"},"counting"),Object(a.b)("li",{parentName:"ul"},"true/false"))),Object(a.b)("li",{parentName:"ul"},"State Representation:",Object(a.b)("ul",{parentName:"li"},Object(a.b)("li",{parentName:"ul"},"State is usually represented by index (i) or (i, j)"),Object(a.b)("li",{parentName:"ul"},"is represented by dp","[i]"," and dp","[i][j]",", which are the most optimal solutions for a","[i]"," or a","[i][j]"))),Object(a.b)("li",{parentName:"ul"},"Transition:",Object(a.b)("ul",{parentName:"li"},Object(a.b)("li",{parentName:"ul"},"Initalization is usually just ",Object(a.b)("inlineCode",{parentName:"li"},"dp[0]")," with ",Object(a.b)("inlineCode",{parentName:"li"},"a[0]")," or ",Object(a.b)("inlineCode",{parentName:"li"},"a[dp.length-1]")," with ",Object(a.b)("inlineCode",{parentName:"li"},"a[a.length-1]")),Object(a.b)("li",{parentName:"ul"},"At each index i, the most optimal solutions of the surrounding neighbors should be found already"),Object(a.b)("li",{parentName:"ul"},"Update ",Object(a.b)("inlineCode",{parentName:"li"},"dp[i]")," or ",Object(a.b)("inlineCode",{parentName:"li"},"dp[i,j]")," with an aggregate function with the values of its neighbors")))))}s.isMDXComponent=!0},147:function(e,t,n){"use strict";function r(){return(r=Object.assign||function(e){for(var t=1;t<arguments.length;t++){var n=arguments[t];for(var r in n)Object.prototype.hasOwnProperty.call(n,r)&&(e[r]=n[r])}return e}).apply(this,arguments)}n.d(t,"a",(function(){return r}))},148:function(e,t,n){"use strict";n.d(t,"a",(function(){return b})),n.d(t,"b",(function(){return m}));var r=n(0),i=n.n(r);function a(e,t,n){return t in e?Object.defineProperty(e,t,{value:n,enumerable:!0,configurable:!0,writable:!0}):e[t]=n,e}function o(e,t){var n=Object.keys(e);if(Object.getOwnPropertySymbols){var r=Object.getOwnPropertySymbols(e);t&&(r=r.filter((function(t){return Object.getOwnPropertyDescriptor(e,t).enumerable}))),n.push.apply(n,r)}return n}function c(e){for(var t=1;t<arguments.length;t++){var n=null!=arguments[t]?arguments[t]:{};t%2?o(Object(n),!0).forEach((function(t){a(e,t,n[t])})):Object.getOwnPropertyDescriptors?Object.defineProperties(e,Object.getOwnPropertyDescriptors(n)):o(Object(n)).forEach((function(t){Object.defineProperty(e,t,Object.getOwnPropertyDescriptor(n,t))}))}return e}function u(e,t){if(null==e)return{};var n,r,i=function(e,t){if(null==e)return{};var n,r,i={},a=Object.keys(e);for(r=0;r<a.length;r++)n=a[r],t.indexOf(n)>=0||(i[n]=e[n]);return i}(e,t);if(Object.getOwnPropertySymbols){var a=Object.getOwnPropertySymbols(e);for(r=0;r<a.length;r++)n=a[r],t.indexOf(n)>=0||Object.prototype.propertyIsEnumerable.call(e,n)&&(i[n]=e[n])}return i}var l=i.a.createContext({}),s=function(e){var t=i.a.useContext(l),n=t;return e&&(n="function"==typeof e?e(t):c(c({},t),e)),n},b=function(e){var t=s(e.components);return i.a.createElement(l.Provider,{value:t},e.children)},p={inlineCode:"code",wrapper:function(e){var t=e.children;return i.a.createElement(i.a.Fragment,{},t)}},d=i.a.forwardRef((function(e,t){var n=e.components,r=e.mdxType,a=e.originalType,o=e.parentName,l=u(e,["components","mdxType","originalType","parentName"]),b=s(n),d=r,m=b["".concat(o,".").concat(d)]||b[d]||p[d]||a;return n?i.a.createElement(m,c(c({ref:t},l),{},{components:n})):i.a.createElement(m,c({ref:t},l))}));function m(e,t){var n=arguments,r=t&&t.mdxType;if("string"==typeof e||r){var a=n.length,o=new Array(a);o[0]=d;var c={};for(var u in t)hasOwnProperty.call(t,u)&&(c[u]=t[u]);c.originalType=e,c.mdxType="string"==typeof e?e:r,o[1]=c;for(var l=2;l<a;l++)o[l]=n[l];return i.a.createElement.apply(null,o)}return i.a.createElement.apply(null,n)}d.displayName="MDXCreateElement"},149:function(e,t,n){"use strict";function r(e,t){if(null==e)return{};var n,r,i={},a=Object.keys(e);for(r=0;r<a.length;r++)n=a[r],t.indexOf(n)>=0||(i[n]=e[n]);return i}n.d(t,"a",(function(){return r}))},332:function(e,t,n){"use strict";n.r(t),t.default=n.p+"assets/images/Matrix-71cbbbb576683542d39030e54d03f200.jpg"}}]);