2b:null 2c:["$","title",null,{"children":"Dynamic Programming with Coins | Kevin Xu | Observable"}] 31:Tbcd,splashViz = { const vizWidth = 600; const height = 300; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(stratifiedData); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['quarter', 'dime', 'nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['green', 'orange', 'red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", 3) // .attr("stroke-opacity", d => +d.target.data.amount >= 0 ? 1 : 0.4) .attr("stroke-opacity", 0.8) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") // .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) .attr("opacity", 0.8) .attr("cx", d => d.x) .attr("cy", d => d.y); // node.append("text") // .attr("stroke", "white") // .attr("paint-order", "stroke") // .attr("fill", "black") // .attr("x", d => d.x) // .attr("y", d => d.y) // .attr("text-anchor", "middle") // .attr("alignment-baseline", "middle") // .attr("dy", 14) // .attr("font-size", 15) // .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) // .text(d => d.data.amount) const legendGroup = svg.append("g").selectAll("g") .data(coins) .enter().append("g"); // legendGroup.append("text") // .text(d => d) // .attr("font-size", 14) // .attr("x", 500) // .attr("y", (d, i) => 16 * i + 30) // legendGroup.append("rect") // .attr("x", 475) // .attr("y", (d, i) => 16 * i + 20) // .attr("width", 20) // .attr("height", 12) // .attr("opacity", 0.8) // .attr("fill", d => colorScale(d)); // treeGroup.append("text") // .attr("x", 20) // .attr("y", 250) // .attr("font-size", 12) // .text("Reduced opacity signifies nodes/paths that lead to negative values.") return svg.node(); }32:T9f0,md` ### Minimum Number of Coins Required to Make Change #### Problem Statement In this variation, we're asked to find the minimum number of coins required to make change for a certain amount of money. We're given a set of denominations (i.e., values of coins, such as quarters, dimes, nickels, etc., for those in the U.S.) that we have to work with. For example, the minimum number of coins required to make change for $0.07 is 3 -- we need 1 nickel and 2 pennies. Let's set up the problem so that we're working with the official U.S. coin denominations: - dollar coin ($1.00) - half-dollar coin ($0.50) - quarter ($0.25) - dime ($0.10) - nickel ($0.05) - penny ($0.01) Additionally, we've got an unlimited supply of each coin. #### The Intuition This was one of the most confusing things for me to wrap my head around. When I have to make change in real life, the usual thought process I go through is to start from the largest denomination coin that is less than or equal to the change amount, subtract that from the change amount, and then repeat for the remainder. For example, if I needed to make change for $0.07, I would see that the nickel is the largest denomination coin that is less than or equal to $0.07, and then find the largest denomination coin that is less than or equal to $0.02 (since $0.07 - $0.05 = $0.02), etc., and then hand over my hard-earned nickel and 2 pennies. This thought process is referred to as a [*greedy algorithm*](https://en.wikipedia.org/wiki/Greedy_algorithm), where the optimal choice is taken at each step. However, a greedy algorithm does not necessarily find the optimal solution overall, as it's possible that suboptimal choices at certain key points could lead to the best outcome overall. #### Dynamic Programming -- Brute Force With Perfect Memory In contrast to how I would think about this in real life, in order to solve the coin change problem with dynamic programming, the approach is more akin to brute force (i.e., attempting all possible combinations), with optimizations to avoid redundant computations. The algorithm involves trying every possible coin at each step of the way, producing a tree of coin choices, and then comparing the total number of coins required for each path. In order to illustrate this, let's use the relatively simple case of having to make change for $0.07, and let's assume that we only have 4 coins to work with: - quarter ($0.25) - dime ($0.10) - nickel ($0.05) - penny ($0.01) First, let's take inventory of where we can go, starting from $0.07: `33:Td6d,firstPaths = { const vizWidth = 600; const height = 150; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(d3.stratify() .id(d => d.id) .parentId(d => d.parent) ([ {"amount": "7", "parent": "", "id": "root"}, {"amount": "-18", "parent": "root", "id": "q"}, {"amount": "-3", "parent": "root", "id": "d"}, {"amount": "2", "parent": "root", "id": "n"}, {"amount": "6", "parent": "root", "id": "p"} ])); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['quarter', 'dime', 'nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['green', 'orange', 'red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => +d.target.data.amount >= 0 ? 1 : 0.4) .attr("stroke-opacity", 0.8) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") // .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) .attr("opacity", 0.8) .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", 15) // .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) //.attr("opacity", 0.8) .text(d => d.data.amount) const legendGroup = svg.append("g").selectAll("g") .data(coins) .enter().append("g"); legendGroup.append("text") .text(d => d) .attr("font-size", 14) .attr("x", width > 600 ? vizWidth - 100 : width * 0.75) .attr("y", (d, i) => 16 * i + 30) legendGroup.append("rect") .attr("x", width > 600 ? vizWidth - 125 : width * 0.75 - 25) .attr("y", (d, i) => 16 * i + 20) .attr("width", 20) .attr("height", 12) .attr("opacity", 0.8) .attr("fill", d => colorScale(d)); // treeGroup.append("text") // .attr("x", 20) // .attr("y", 250) // .attr("font-size", 12) // .text("Reduced opacity signifies nodes/paths that lead to negative values.") return svg.node(); }34:Td0a,secondPaths = { const vizWidth = 600; const height = 260; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - 60])(d3.stratify() .id(d => d.id) .parentId(d => d.parent) ([ {"amount": "7", "parent": "", "id": "root"}, {"amount": "2", "parent": "root", "id": "n"}, {"amount": "6", "parent": "root", "id": "p"}, {"amount": "-23", "parent": "n", "id": "nq"}, {"amount": "-8", "parent": "n", "id": "nd"}, {"amount": "-3", "parent": "n", "id": "nn"}, {"amount": "1", "parent": "n", "id": "np"}, {"amount": "-19", "parent": "p", "id": "pq"}, {"amount": "-4", "parent": "p", "id": "pd"}, {"amount": "1", "parent": "p", "id": "pn"}, {"amount": "5", "parent": "p", "id": "pp"} ])); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['quarter', 'dime', 'nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['green', 'orange', 'red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => +d.target.data.amount >= 0 ? 1 : 0.4) .attr("stroke-opacity", 0.8) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", 15) .text(d => d.data.amount) const legendGroup = svg.append("g").selectAll("g") .data(coins) .enter().append("g"); legendGroup.append("text") .text(d => d) .attr("font-size", 14) .attr("x", width > 600 ? vizWidth - 100 : width * 0.75) .attr("y", (d, i) => 16 * i + 30) legendGroup.append("rect") .attr("x", width > 600 ? vizWidth - 125 : width * 0.75 - 25) .attr("y", (d, i) => 16 * i + 20) .attr("width", 20) .attr("height", 12) .attr("opacity", 0.8) .attr("fill", d => colorScale(d)); return svg.node(); }35:Tbe1,allPaths = { const vizWidth = 600; const height = 300; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(stratifiedData); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['quarter', 'dime', 'nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['green', 'orange', 'red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => +d.target.data.amount >= 0 ? 1 : 0.4) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", width > 600 ? 15 : "0.6rem") .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) .text(d => d.data.amount) const legendGroup = svg.append("g").selectAll("g") .data(coins) .enter().append("g"); legendGroup.append("text") .text(d => d) .attr("font-size", 14) .attr("x", width > 600 ? vizWidth - 100 : width * 0.75) .attr("y", (d, i) => 16 * i + 30) legendGroup.append("rect") .attr("x", width > 600 ? vizWidth - 125 : width * 0.75 - 25) .attr("y", (d, i) => 16 * i + 20) .attr("width", 20) .attr("height", 12) .attr("opacity", 0.8) .attr("fill", d => colorScale(d)); treeGroup.append("text") .attr("x", 20) .attr("y", 250) .attr("font-size", width > 600 ? 15 : "0.6rem") .text("Abandoned paths have reduced opacity.") return svg.node(); }36:Tb53,validPaths = { const stratifiedValidData = d3.stratify() .id(d => d.id) .parentId(d => d.parent) (data7Valid) const vizWidth = 600; const height = 300; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(stratifiedValidData); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => +d.target.data.amount >= 0 ? 1 : 0.4) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", 15) .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.4) .text(d => d.data.amount) const legendGroup = svg.append("g").selectAll("g") .data(coins) .enter().append("g"); legendGroup.append("text") .text(d => d) .attr("font-size", 14) .attr("x", width > 600 ? vizWidth - 100 : width * 0.75) .attr("y", (d, i) => 16 * i + 30) legendGroup.append("rect") .attr("x", width > 600 ? vizWidth - 125 : width * 0.75 - 25) .attr("y", (d, i) => 16 * i + 20) .attr("width", 20) .attr("height", 12) .attr("fill", d => colorScale(d)); return svg.node(); }37:Tc16,validPath1 = { const routeIds = ['root', 'n', 'np', 'npp']; const stratifiedValidData = d3.stratify() .id(d => d.id) .parentId(d => d.parent) (data7Valid) const vizWidth = 600; const height = 300; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(stratifiedValidData); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => routeIds.includes(d.target.id) ? 1 : 0.3) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.3) .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", 15) .attr("opacity", d => routeIds.includes(d.id) ? 1 : 0.3) .text(d => d.data.amount) const legendGroup = svg.append("g").selectAll("g") .data(coins) .enter().append("g"); legendGroup.append("text") .text(d => d) .attr("font-size", 14) .attr("x", width > 600 ? vizWidth - 100 : width * 0.75) .attr("y", (d, i) => 16 * i + 30) legendGroup.append("rect") .attr("x", width > 600 ? vizWidth - 125 : width * 0.75 - 25) .attr("y", (d, i) => 16 * i + 20) .attr("width", 20) .attr("height", 12) .attr("fill", d => colorScale(d)); treeGroup.append("text") .attr("x", 5) .attr("y", 170) .attr("font-size", 12) .text("Path 1. Total Weight: 3 coins.") return svg.node(); }38:Tac2,validPath2 = { const routeIds = ['root', 'p', 'pn', 'pnp']; const stratifiedValidData = d3.stratify() .id(d => d.id) .parentId(d => d.parent) (data7Valid) const vizWidth = 600; const height = 300; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(stratifiedValidData); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => routeIds.includes(d.target.id) ? 1 : 0.3) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.3) .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", 15) .attr("opacity", d => routeIds.includes(d.id) ? 1 : 0.3) .text(d => d.data.amount) treeGroup.append("text") .attr("x", () => { const path2CenterNode = root.descendants().find(d => d.id === 'pnp'); return path2CenterNode.x; }) .attr("y", 170) .attr("text-anchor", "middle") .attr("font-size", 12) .text("Path 2. Total Weight: 3 coins.") return svg.node(); }39:Tac4,validPath3 = { const routeIds = ['root', 'p', 'pp', 'ppn']; const stratifiedValidData = d3.stratify() .id(d => d.id) .parentId(d => d.parent) (data7Valid) const vizWidth = 600; const height = 300; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(stratifiedValidData); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => routeIds.includes(d.target.id) ? 1 : 0.3) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.3) .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", 15) .attr("opacity", d => routeIds.includes(d.id) ? 1 : 0.3) .text(d => d.data.amount) treeGroup.append("text") .attr("x", () => { const path3CenterNode = root.descendants().find(d => d.id === 'ppn'); return path3CenterNode.x + 30; }) .attr("y", 170) .attr("text-anchor", "end") .attr("font-size", 12) .text("Path 3. Total Weight: 3 coins.") return svg.node(); }3a:Tb64,validPath4 = { const routeIds = ['root', 'p', 'pp', 'ppp', 'pppp', 'ppppp', 'pppppp', 'ppppppp']; const stratifiedValidData = d3.stratify() .id(d => d.id) .parentId(d => d.parent) (data7Valid) const vizWidth = 600; const height = 300; const svg = d3.select(DOM.svg(width > 600 ? vizWidth : width, height)); const root = d3.tree().size([width > 600 ? vizWidth : width - margin.left - margin.right, height - margin.top - margin.bottom])(stratifiedValidData); // console.log('root.descendants()', root.descendants()); // console.log('root.links()', root.links()); const coins = ['nickel', 'penny']; const colorScale = d3.scaleOrdinal() .domain(coins) .range(['red', 'blue']); const treeGroup = svg.append("g"); const link = treeGroup.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("transform", `translate(0, ${margin.top})`) .selectAll("path") .data(root.links()) .enter().append("path") .attr("d", d3.linkVertical() .x(d => d.x) .y(d => d.y)) .attr("stroke-width", pathWidth) .attr("stroke-opacity", d => routeIds.includes(d.target.id) ? 1 : 0.3) .attr("stroke", d => { if (d.source.data.amount - d.target.data.amount === 5) { return 'red'; } else if (d.source.data.amount - d.target.data.amount === 25) { return 'green'; } else if (d.source.data.amount - d.target.data.amount === 1) { return 'blue'; } else if (d.source.data.amount - d.target.data.amount === 10) { return 'orange'; } }); const node = treeGroup.append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("transform", `translate(0, ${margin.top})`) .selectAll("g") .data(root.descendants()) .enter().append("g") node.append("circle").attr("r", 4) .attr("fill", "black") .attr("opacity", d => d.data.amount >= 0 ? 1 : 0.3) .attr("cx", d => d.x) .attr("cy", d => d.y); node.append("text") .attr("stroke", "white") .attr("stroke-width", 3) .attr("stroke-opacity", 0.8) .attr("paint-order", "stroke") .attr("fill", "black") .attr("x", d => d.x) .attr("y", d => d.y) .attr("text-anchor", "middle") .attr("alignment-baseline", "middle") .attr("dy", 14) .attr("font-size", 15) .attr("opacity", d => routeIds.includes(d.id) ? 1 : 0.3) .text(d => d.data.amount) treeGroup.append("text") .attr("x", () => { return root.descendants().find(d => d.id === 'ppppppp').x - 20; }) .attr("y", () => { const path4CenterNode = root.descendants().find(d => d.id === 'ppppppp'); return path4CenterNode.y; }) .attr("alignment-baseline", "hanging") .attr("text-anchor", "end") .attr("font-size", 12) .text("Path 4. Total Weight: 7 coins.") return svg.node(); }3b:T6b8,md` #### Recursive Implementation with Memoization In order to avoid unnecessary computations, we'll want to use a data structure that allows us to efficiently store and retrieve previously calculated minimum weights. JavaScript offers a few different options for us. We could use: - An [Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array), where the index of the array represent an amount and the value at that index would be the minimum number of coins required to make change for that amount. For example, an array of \`[0, 1, 2, 3]\` would indicate that 0 coins are required to make change for $0.00, while 3 coins are required to make change for $0.03. - An [Object](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object), where key:value pairs store previously computed records. In order to represent the same data as above, we'd use an object of \`{"0": 0, "1": 1, "2": 2, "3":3}\`. - A [Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map), where key:value pairs store previously computed records. For this problem, an array would probably be the most intuitive type to use, since it's possible to structure the problem so that we can work with integer numbers of cents. However, Maps were made for this kind of thing, so let's try out both. Note: an Object would work fine, but Object keys can only be strings and Symbols, which isn't exactly what we're working with. When we use numbers for keys, they'll get coerced into strings without any ill-effects in our case, but why use an Object for this purpose when Maps are available? ##### Recursive Implementation with Memoization Using a Map `3c:T549,js(`const coins = [1, 5, 10, 25, 50, 100]; let changeTable = new Map(); function makeChange(value) { if (value === 0) { return 0; } else { // if changeTable already has a solution, just use this solution rather than continuing on if (changeTable.has(value)) { return changeTable.get(value); } let minFound = Infinity; for (let coin of coins) { if (value - coin >= 0) { let minForThisPath = makeChange(value - coin) + 1; // check if there's a previously recorded solution if (changeTable.has(value)) { // check if this solution is better than the previously recorded solution if (minForThisPath < changeTable.get(value)) { changeTable.set(value, minForThisPath); } } else { // since there's no previously recorded solution, add this solution changeTable.set(value, minForThisPath); } if (minForThisPath < minFound) { minFound = minForThisPath; } } } return minFound; } } console.log(makeChange(0), 'should equal 0'); console.log(makeChange(5), 'should equal 1'); console.log(makeChange(6), 'should equal 2'); console.log(makeChange(7), 'should equal 3'); console.log(makeChange(75), 'should equal 2'); console.log(makeChange(78), 'should equal 5');`)3d:T406,js(`function makeChange(value) { const coins = [1, 5, 10, 25, 50, 100]; let changeTable = new Map([[0, 0]]); // iterate up to and including the value we want to solve for for (let i = 1; i <= value; i++) { // iterate through each coin to try every possibility for (let coin of coins) { // if i - coin is 0, then we know it took only 1 coin to make change for i if (i - coin === 0) { changeTable.set(i, 1); } else if (i - coin > 0) { // if i - coin > 0, then we should already have a solution for i - coin, // so we just need to add 1 to the previously recorded solution changeTable.set(i, 1 + changeTable.get(i - coin)); } } } return changeTable.get(value); } console.log(makeChange(0), 'should equal 0'); console.log(makeChange(5), 'should equal 1'); console.log(makeChange(6), 'should equal 2'); console.log(makeChange(7), 'should equal 3'); console.log(makeChange(75), 'should equal 2'); console.log(makeChange(78), 'should equal 5');`)3e:T81f,data7 = [ {"amount": "7", "parent": "", "id": "root"}, {"amount": "-18", "parent": "root", "id": "q"}, {"amount": "-3", "parent": "root", "id": "d"}, {"amount": "2", "parent": "root", "id": "n"}, {"amount": "-23", "parent": "n", "id": "nq"}, {"amount": "-8", "parent": "n", "id": "nd"}, {"amount": "-3", "parent": "n", "id": "nn"}, {"amount": "1", "parent": "n", "id": "np"}, {"amount": "-24", "parent": "np", "id": "npq"}, {"amount": "-9", "parent": "np", "id": "npd"}, {"amount": "-4", "parent": "np", "id": "npn"}, {"amount": "0", "parent": "np", "id": "npp"}, {"amount": "6", "parent": "root", "id": "p"}, {"amount": "-19", "parent": "p", "id": "pq"}, {"amount": "-4", "parent": "p", "id": "pd"}, {"amount": "1", "parent": "p", "id": "pn"}, {"amount": "-24", "parent": "pn", "id": "pnq"}, {"amount": "-9", "parent": "pn", "id": "pnd"}, {"amount": "-4", "parent": "pn", "id": "pnn"}, {"amount": "0", "parent": "pn", "id": "pnn"}, {"amount": "5", "parent": "p", "id": "pp"}, {"amount": "-20", "parent": "pp", "id": "ppq"}, {"amount": "-5", "parent": "pp", "id": "ppd"}, {"amount": "0", "parent": "pp", "id": "ppn"}, {"amount": "4", "parent": "pp", "id": "ppp"}, {"amount": "-21", "parent": "ppp", "id": "pppq"}, {"amount": "-6", "parent": "ppp", "id": "pppd"}, {"amount": "-1", "parent": "ppp", "id": "pppn"}, {"amount": "3", "parent": "ppp", "id": "pppp"}, {"amount": "-22", "parent": "pppp", "id": "ppppq"}, {"amount": "-7", "parent": "pppp", "id": "ppppd"}, {"amount": "-2", "parent": "pppp", "id": "ppppn"}, {"amount": "2", "parent": "pppp", "id": "ppppp"}, {"amount": "-23", "parent": "ppppp", "id": "pppppq"}, {"amount": "-8", "parent": "ppppp", "id": "pppppd"}, {"amount": "-3", "parent": "ppppp", "id": "pppppn"}, {"amount": "1", "parent": "ppppp", "id": "pppppp"}, {"amount": "-24", "parent": "pppppp", "id": "ppppppq"}, {"amount": "-9", "parent": "pppppp", "id": "ppppppd"}, {"amount": "-4", "parent": "pppppp", "id": "ppppppn"}, {"amount": "0", "parent": "pppppp", "id": "ppppppp"}, ]3f:[] 2f:{"id":"c830c6f14af79ce2","slug":"dynamic-programming-with-coins","title":"Dynamic Programming with Coins","thumbnail":"2fb1d1261a4df5414f668deeeaf34a2720c22a861d0b1792e9c2d522a2866f48","access_level":"public","create_time":"$D2019-02-10T22:40:24.455Z","update_time":"$D2020-07-03T22:48:14.531Z","view_time":null,"first_public_time":"$D2019-03-23T05:03:27.679Z","fork":false,"stars":11,"starred":false,"owner":{"type":"team","id":"f04c66ca9cd6f30f","login":"khxu","name":"Kevin Xu","avatar_url":"https://avatars-next.observableusercontent.com/95f43d42f7b1b38b7500f5536a36649032e80656a3012bd0a58eded804edc8d6","tier":"starter_2024"},"version":1600,"publish_version":1600,"role":null,"authored":false,"authors":[{"type":"individual","id":"d78350930352ba0b","login":"khxu","name":"Kevin Xu","avatar_url":"https://avatars-next.observableusercontent.com/95f43d42f7b1b38b7500f5536a36649032e80656a3012bd0a58eded804edc8d6","tier":null}],"members":[{"type":"individual","id":"d78350930352ba0b","login":"khxu","name":"Kevin Xu","avatar_url":"https://avatars-next.observableusercontent.com/95f43d42f7b1b38b7500f5536a36649032e80656a3012bd0a58eded804edc8d6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Dynamic Programming with Coins","cells":[{"id":0,"value":"md`# Dynamic Programming with Coins`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":919,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6,"value":"md`\nDynamic programming is tricky. Here's the walkthrough (with data visualizations!) that I wish I'd found when I began trying to figure this out.\n\n## The Coin Change Problem\nThere are a few different variants of the coin change problem. For this post, we'll stick to one of the simpler variants in order to really focus on illustrating the thought process.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":12,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":754,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":776,"value":"md`\nGreat, if we start from $0.07, it looks like we can get to: \n- -$0.18 if we use a quarter; \n- -$0.03 if we use a dime; \n- $0.02 if we use a nickel; or \n- $0.06 if we use a penny. \n\nSince our goal is to get to $0.00, we shouldn't go any further down the paths that lead to negative amounts, so let's keep exploring the non-negative paths:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":785,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":799,"value":"md`\nAlright, we're gaining some more useful information here. Now, we know that if we start from $0.07, we can get to:\n- -$0.23 if we use a nickel and then a quarter;\n- -$0.08 if we use a nickel and then a dime;\n- -$0.03 if we use a nickel and then another nickel;\n- $0.01 if we use a nickel and then a penny;\n- -$0.19 if we use a penny and then a quarter;\n- -$0.04 if we use a penny and then a dime;\n- $0.01 if we use a penny and then a nickel; or\n- $0.05 if we use a penny and then another penny.\n\nAt this point, let's just go ahead and build out the full tree:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":72,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":77,"value":"md`\nAs you can see, every possible coin is attempted at each step. If including a particular coin leads to a negative value, then we abandon that path.\n\nNow, let's prune our tree a bit to see the valid paths more cleanly:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":87,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":86,"value":"md`\nBut what now? From here, we need one more insight: each edge of this tree has a weight of 1 coin, meaning that in order to go from one node to the next, we had to add one coin to the amount of change we would give. In the end, we want to provide exact change, so we need to compare all of the paths that led from $0.07 to $0.00. Furthermore, because we want the *minimum* number of coins required for a given amount of change, we need to identify the path that has the least total weight.\n\nTo be clear, here are the 4 paths we need to compare:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":361,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":381,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":390,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":394,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":405,"value":"md`\nYou've probably noticed that Paths 1, 2, and 3 are quite similar -- they all use exactly 1 nickel and 2 pennies to make change for $0.07. The only difference is the order in which each coin is used. For this variant of the problem, we only care about the minimum number of coins, but we could use this information for other variations that, for example, ask us to return all possible combinations or permutations of coins that are required to make change. \n\nIn any case, we've arrived at our answer: 3 coins is the minimum number of coins required to make change for $0.07, if we're given quarters, dimes, nickels, and pennies.\n\nWhew, okay, that was all well and good, but we still haven't done any coding to actually implement this algorithm. Let's dive into it.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":99,"value":"md`\n#### Recursive Implementation\nFirst, let's come up with a recursive solution for this problem. In order to do that, our first step is to identify the base cases.\n\nOne base case is if we need to make change for $0.00. Easy -- the minimum number of coins needed to make $0.00 is 0 coins. Interestingly, in the case of the coin change problem where we have pennies to work with, this is actually the only base case we need in order to come up with a recursive solution.\n\nHere's the initial setup:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":535,"value":"js(`const coins = [1, 5, 10, 25, 50, 100];\n\nfunction makeChange(amount) {\n if (amount === 0) {\n return 0;\n }\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":538,"value":"md`Take a few minutes to think about how we would continue on. We eventually need to recursively call the \\`makeChange()\\` function but how do we get there? What do we need to keep track of?\n\nPicture the tree from a few figures ago. Ultimately, we need to compare the total weights of all of the paths that lead from the starting amount to $0.00. Therefore, we need to keep track of the minimum total weight of all paths calculated so far.\n\nHere's how we can do that:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":540,"value":"js(`const coins = [1, 5, 10, 25, 50, 100];\n\nfunction makeChange(amount) {\n if (amount === 0) {\n return 0;\n } else {\n let minFound = Infinity;\n \n // iterate through each coin to try every possibility\n for (let coin of coins) {\n\n // if using this coin leads to a valid (i.e., non-negative) path\n if (amount - coin >= 0) {\n\n // recursively call makeChange() on the remaining amount and add 1 for using this coin\n let minForThisPath = makeChange(amount - coin) + 1;\n\n // after we finish recursing, if this minimum is the lowest found so far, replace minFound\n if (minForThisPath < minFound) {\n minFound = minForThisPath;\n }\n }\n }\n return minFound;\n }\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":543,"value":"md`Cool. Stepping through the code: first, we've got recursive calls that only resolve when \\`makeChange()\\` is called with an \\`amount\\` of 0, as you can see from the base case:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":545,"value":"js(`if (amount === 0) {\n return 0;\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":549,"value":"md`Additionally, if \\`amount - coin < 0\\`, then no recursive call is made, as you can see here:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":550,"value":"js(`if (amount - coin >= 0) {\n let minFoundForThisPath = makeChange(amount - coin) + 1;\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":554,"value":"md`Lastly, we keep track of the minimum in the \\`minFound\\` variable and update each time a new minimum weight is found. Once we go through all of the possibilities, we return \\`minFound\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":816,"value":"js(`\nif (minFoundForThisPath < minFound) {\n minFound = minFoundForThisPath;\n}\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":452,"value":"md`\n#### Shoulder Pats\nGreat work, we've got a solution. But wait! We're repeating the same computations over and over again with this implementation. Each time we land on an \\`amount\\` where \\`amount - coin >= 0\\`, we'll recurse again and again until we get back to calling \\`makeChange(0)\\`. This is where memoization comes into play. But first, let's take a step back and examine where we're at.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":340,"value":"md`\n## Dynamic Programming as an Approach\nGenerally, the idea is to:\n1. break down the problem into smaller sub-problems;\n2. record the solution to each sub-problem so that we don't have to re-calculate solutions that have already been computed; and\n3. combine the solutions of sub-problems to calculate the solution you actually want\n\nCurrently, our recursive implementation handles Steps 1 and 3 just fine. However, Step 2 -- also referred to as *memoization* -- is missing.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":489,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":530,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":500,"value":"md`\nIf a value exists in the \\`changeTable\\`, instead of recalculating, we'll just return the existing record: \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":524,"value":"js(`if (changeTable.has(value)) {\n return changeTable.get(value);\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":527,"value":"md`However, if a new minimum number of coins is found for a particular amount that is less than the value stored in \\`changeTable\\`, we'll overwrite that record to store the new minimum:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":516,"value":"js(`if (changeTable.has(value)) {\n if (minForThisPath < changeTable.get(value)) {\n changeTable.set(value, minForThisPath);\n }\n} else {\n changeTable.set(value, minForThisPath);\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":532,"value":"md`\nAs a result, this essentially creates base cases for every value of \\`amount\\` that we have stored as a key in our \\`Map\\`, thereby avoiding having to get all the way down to \\`makeChange(0)\\` to finally stop recursing.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":571,"value":"md`\n---\n##### Recursive Implementation with Memoization Using an Array\nThis is the same recursive algorithm, but it uses an Array for memoization rather than a Map:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":575,"value":"js(`\nconst coins = [1, 5, 10, 25, 50, 100];\n\nlet changeTable = [];\n\nfunction makeChange(value) {\n if (value === 0) {\n return 0;\n } else {\n if (changeTable[value] != undefined) {\n return changeTable[value];\n }\n\n let minFound = Infinity;\n\n for (let coin of coins) {\n if (value - coin >= 0) {\n let minForThisPath = makeChange(value - coin) + 1;\n\n if (changeTable[value] != undefined) {\n if (minForThisPath < changeTable[value]) {\n changeTable[value] = minForThisPath;\n }\n } else {\n changeTable[value] = minForThisPath;\n }\n\n if (minForThisPath < minFound) {\n minFound = minForThisPath;\n }\n\n }\n }\n\n return minFound;\n }\n}\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":586,"value":"md`\nGreat, so we've got a recursive implementation working with memoization. However, recursive solutions suffer from the fact that the computer allocates memory for each recursive function call and will run out of available memory if too many of those function calls build up. Just in case this is an issue, whether because we'll need to use this algorithm in memory-limited devices or for very large values, let's implement an iterative version.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":592,"value":"md`#### Iterative Implementation with Memoization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":597,"value":"md`For the iterative implementation, we'll be taking a *bottom-up* approach, building the \\`changeTable\\` starting from $0.00 up to the amount we actually want. This in contrast to the *top-down* approach that we used in the recursive implementation, where we started from the target amount and then worked backward through recursive calls on lesser amounts of change in order to find the answer.\n\nLet's dive into the code:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":595,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":609,"value":"md`\nConcise, isn't it? \n\nSince we know that the minimum number of coins required to make change for $0.00 is 0 -- the same fact that we used to generate our base case for the recursive implementation -- we first initialize the \\`changeTable\\` with \\`[0, 0]\\`: \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":615,"value":"js(`let changeTable = new Map([[0, 0]]);`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":617,"value":"md`Then, we iterate from $0.01, up to, and including, the value we actually want to make change for:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":621,"value":"js('for (let i = 1; i <= value; i++)')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":626,"value":"md`\nFrom there, with each additional cent, we iterate through each coin to see if:\n1. \\`amount - coin\\` is equal to 0, in which case we know that 1 coin is enough to make change for the given amount; or\n2. \\`amount - coin\\` is a positive number, in which case we know that the previously stored number of coins + the given coin would be enough to make change for the given amount.\n\nIf the first condition is true, then we set the \\`changeTable\\` to 1 for that amount, since 1 is the minimum number of coins required to make change for a non-zero amount of money:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":635,"value":"js(`if (i - coin === 0) {\n changeTable.set(i, 1);\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":638,"value":"md`Alternatively, if the second condition is true, then we set the \\`changeTable\\` to 1 + the previously stored value:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":640,"value":"js(`else if (i - coin > 0) {\n changeTable.set(i, 1 + changeTable.get(i - coin));\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":642,"value":"md`It's important to also note here that the \\`coins\\` array needs to be sorted from low to high, since we rely on the previously stored records in the \\`changeTable\\`, and the penny coin guarantees that there will be a valid value at every cent from $0.01 to the amount we're looking for. Thus, we initialized the \\`coins\\` array to be:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":648,"value":"js(`const coins = [1, 5, 10, 25, 50, 100];`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1426,"value":"md`However, if we can't guarantee the sort order of the coins, we can add an additional check in order to make sure that only the most optimal solution is recorded in the \\`changeTable\\` -- full solution below:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1430,"value":"js(`function makeChange(value) {\n // const coins = [1, 5, 10, 25, 50, 100];\n const coins = [100, 50, 25, 10, 5, 1];\n \n let changeTable = new Map([[0, 0]]);\n \n for (let i = 1; i <= value; i++) {\n\n for (let coin of coins) {\n\n if (i - coin === 0) {\n changeTable.set(i, 1);\n } else if (i - coin > 0) {\n if (changeTable.has(i)) {\n if (changeTable.get(i) > changeTable.get(i - coin) + 1) {\n changeTable.set(i, 1 + changeTable.get(i - coin));\n }\n } else {\n changeTable.set(i, 1 + changeTable.get(i - coin));\n }\n }\n\n }\n\n }\n return changeTable.get(value);\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":826,"value":"md`\n# Testing\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1258,"value":"md`Drag the slider below to run the memoized algorithms with different values.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":847,"value":"viewof changeAmount = slider({\n min: 0, \n max: 300, \n step: 1, \n value: 150, \n title: \"Change Amount\", \n description: \"Amount of $ to make change for, in cents\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":849,"value":"md`Minimum number of coins to needed to make change for ${d3.format(\"($.2f\")(changeAmount / 100)} calculated using the recursive algorithm: ${makeChangeRecursive(changeAmount)}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":867,"value":"md`Minimum number of coins to needed to make change for ${d3.format(\"($.2f\")(changeAmount / 100)} calculated using the iterative algorithm: ${makeChangeIterative(changeAmount)}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1309,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1381,"value":"md`Click the button below to re-run the speed tests.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1296,"value":"viewof speedTest = button({\n value: \"Run\", \n description: \"Re-runs the speed tests for the algorithms. Results will vary based on your browser and device.\",\n title: \"Speed Test\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1328,"value":"{\n speedTest;\n return md\n `Type | Number of Times Function was Executed | Time Required (ms)\n:---:|:---:|:---:\nRecursive, not memoized | 40 | ${recursiveNonMemoizedTestResults}\nRecursive, memoized | 200 | ${recursiveMemoizedTestResults}\nIterative, memoized | 200 | ${iterativeMemoizedTestResults}\n `\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1384,"value":"md`As you can see, the memoized algorithms are much faster, returning answers for $0.00 to $2.00 in ~20-25% of the time it takes the non-memoized algorithm to return answers for just $0.00 to $0.40.\n\nWhy the difference in number of executions? Well, it took 10+ seconds to run the recursive, non-memoized function on $0.00 through $0.60, while the memoized versions chugged through $0.00 through $0.40 so quickly that they sometimes clocked in at 0 ms (i.e., so quickly that JavaScript's minimum resolution of 1 ms for a Date object wasn't enough to measure the elapsed time). I settled on these numbers through trial and error.\n\nExpand the cells below for more details on the test setup.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1234,"value":"recursiveNonMemoizedTestResults = {\n speedTest;\n const startTime = Date.now();\n \n for (let i = 0; i < 40; i++) {\n makeChangeRecursiveNoMemoize(i)\n }\n \n return Date.now() - startTime;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1255,"value":"recursiveMemoizedTestResults = {\n speedTest;\n const startTime = Date.now();\n \n for (let i = 0; i < 200; i++) {\n makeChangeRecursive(i)\n }\n \n return Date.now() - startTime;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1322,"value":"iterativeMemoizedTestResults = {\n speedTest;\n const startTime = Date.now();\n \n for (let i = 0; i < 200; i++) {\n makeChangeIterative(i)\n }\n \n return Date.now() - startTime;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":839,"value":"function makeChangeRecursive(value) {\n\n const coins = [1, 5, 10, 25, 50, 100];\n \n let changeTable = new Map();\n \n function recurse(value) {\n if (value === 0) {\n return 0;\n } else {\n if (changeTable.has(value)) {\n return changeTable.get(value);\n }\n\n let minFound = Infinity;\n\n for (let coin of coins) {\n if (value - coin >= 0) {\n let minForThisPath = recurse(value - coin) + 1;\n\n if (changeTable.has(value)) {\n if (minForThisPath < changeTable.get(value)) {\n changeTable.set(value, minForThisPath);\n }\n } else {\n changeTable.set(value, minForThisPath);\n }\n\n if (minForThisPath < minFound) {\n minFound = minForThisPath;\n }\n } else {\n }\n }\n return minFound;\n }\n }\n \n return recurse(value);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1231,"value":"function makeChangeRecursiveNoMemoize(value) {\n const coins = [1, 5, 10, 25, 50, 100];\n\n function makeChange(amount) {\n if (amount === 0) {\n return 0;\n } else {\n let minFound = Infinity;\n\n for (let coin of coins) {\n if (amount - coin >= 0) {\n let minForThisPath = makeChange(amount - coin) + 1;\n\n if (minForThisPath < minFound) {\n minFound = minForThisPath;\n }\n }\n }\n return minFound;\n }\n }\n \n return makeChange(value);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":832,"value":"function makeChangeIterative(value) {\n const coins = [1, 5, 10, 25, 50, 100];\n \n let changeTable = new Map([[0, 0]]);\n \n for (let i = 1; i <= value; i++) {\n\n for (let coin of coins) {\n\n if (i - coin === 0) {\n changeTable.set(i, 1);\n } else if (i - coin > 0) {\n if (changeTable.has(i)) {\n if (changeTable.get(i) > changeTable.get(i - coin) + 1) {\n changeTable.set(i, 1 + changeTable.get(i - coin));\n }\n } else {\n changeTable.set(i, 1 + changeTable.get(i - coin));\n }\n }\n\n }\n\n }\n return changeTable.get(value);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":898,"value":"md`\n# The End\n\nThat's all, folks! If you liked the write-up, let me know. If you didn't, keep that to yourself. Just kidding. Feel free to comment.\n\n*Special thanks to Edward Chen for feedback on this article.*\n\n*Also thanks to Fabian Iwand for pointing out that specifying JS in Markdown handles syntax highlighting rather than relying on an external library, like Prism.*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1078,"value":"md`\n---\n# Other Resources/Tutorials Pile\nHere's a list of resources on dynamic programming that I found helpful:\n\n### Medium Posts\n- Omer Goldberg: https://medium.com/@omergoldberg/algorithms-in-js-making-change-bc5dec257e97\n- Phat Le: https://towardsdatascience.com/course-1-algorithmic-toolbox-part-4-dynamic-programming-223ffc01984a\n\n### Data Visualizations\n- VisuAlgo: https://visualgo.net/en/recursion\n- David Galles: https://www.cs.usfca.edu/~galles/visualization/DPChange.html\n\n### Book Excerpts\n- Neil C. Jones and Pavel A. Pevzner: http://bix.ucsd.edu/bioalgorithms/book/excerpt-ch6.pdf\n- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: https://people.eecs.berkeley.edu/~vazirani/algorithms/chap6.pdf\n\n### YouTube Videos\n- MIT OpenCourseWare - Dynamic Programming: https://www.youtube.com/watch?v=OQ5jsbhAv_M&vl=en\n- Tushar Roy - Coding Made Simple: https://www.youtube.com/watch?v=NJuKJ8sasGk&t=108s\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1445,"value":"pathWidth = 5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1438,"value":"data7_bottomUp = [\n {\"amount\": \"0\", \"parent\": \"\", \"id\": \"root\"},\n {\"amount\": \"1\", \"parent\": \"root\", \"id\": \"p\"},\n {\"amount\": \"2\", \"parent\": \"\", \"id\": \"pp\"},\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":54,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":349,"value":"data7Valid = [\n {\"amount\": \"7\", \"parent\": \"\", \"id\": \"root\"},\n {\"amount\": \"2\", \"parent\": \"root\", \"id\": \"n\"},\n {\"amount\": \"1\", \"parent\": \"n\", \"id\": \"np\"},\n {\"amount\": \"0\", \"parent\": \"np\", \"id\": \"npp\"},\n {\"amount\": \"6\", \"parent\": \"root\", \"id\": \"p\"},\n {\"amount\": \"1\", \"parent\": \"p\", \"id\": \"pn\"},\n {\"amount\": \"0\", \"parent\": \"pn\", \"id\": \"pnp\"},\n {\"amount\": \"5\", \"parent\": \"p\", \"id\": \"pp\"},\n {\"amount\": \"0\", \"parent\": \"pp\", \"id\": \"ppn\"},\n {\"amount\": \"4\", \"parent\": \"pp\", \"id\": \"ppp\"},\n {\"amount\": \"3\", \"parent\": \"ppp\", \"id\": \"pppp\"},\n {\"amount\": \"2\", \"parent\": \"pppp\", \"id\": \"ppppp\"},\n {\"amount\": \"1\", \"parent\": \"ppppp\", \"id\": \"pppppp\"},\n {\"amount\": \"0\", \"parent\": \"pppppp\", \"id\": \"ppppppp\"}\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":56,"value":"stratifiedData = d3.stratify()\n .id(d => d.id)\n .parentId(d => d.parent)\n (data7)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4,"value":"d3 = require('d3')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":151,"value":"margin = ({\n top: 20,\n bottom: 20,\n left: 20,\n right: 20\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":511,"value":"function js(codeString) {\n return md`\\`\\`\\`js\\n${codeString}\\n\\`\\`\\``;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":854,"value":"import {slider, button} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W3f","stdlib":"1","titling":"auto"}} 30:"$2f:body"