This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

91. Yang Hui Triangle (Pascical-Triangle)

The label

  • mathematics
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given a non-negative integer numRows, generate the former numRows of the Yanghui triangle.

In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.

Example:

Input: 5 output: [[1], [1, 1], [1, 2, 1],,3,3,1 [1], [1,4,6,4,1]]Copy the code

The basic idea

  1. I’m going to initialize it. I’m going to set all the elements to 1
  2. The next row is going to be the sum of the corresponding elements of the previous row, just looking for the relationship
  3. Save the array, push the result, nothing easy to say.

Writing implement

var generate = function(numRows) {
  let res = []
  for (let i = 0; i < numRows; i++) {
    let curArr = new Array(i + 1).fill(1)
    for (j = 1; j < curArr.length - 1; j++) {
      curArr[j] = res[i - 1][j - 1] + res[i - 1][j]
    }
    res.push(curArr)
  } 
  return res
};

console.log(generate(5))
Copy the code

92. Sum of Minimum Paths of triangles (Pascical-Triangle-II)

The label

  • dp
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given a triangle triangle, find the minimum sum of paths from the top down.

Each step can only move to the next node in the next row. Adjacent nodes in this case are two nodes whose subscripts are the same or equal to the subscripts of the nodes at the previous level + 1. That is, if subscript I is right on the current row, then the next subscript can be moved to I or I + 1 on the next row.

The sample

Input: Triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: As shown in the diagram below: 2 3 4 6 5 7 4 1 8 3 The minimum sum of the top-down paths is 11 (i.e., 2 + 3 + 5 + 1 = 11).Copy the code

The basic idea

Let’s think about it, the minimum path from top to bottom is the same as the minimum path from bottom to top.

And if you’re looking for a path in a two-dimensional array like this, the first one that comes to mind is dp.

If you are not familiar with the basic concepts of dynamic programming, move to DP Basics

Basic steps

Let’s look at it from these three perspectives

  1. Search for optimal substructure (state representation)
  2. Induction of state transition Equation (State calculation)
  3. Boundary initialization
  • State said
    • dp[i][j]Says from the point of(i, j)The edge of theMinimum path sum.
  • State transition equation
    • with(i, j) 点adjacentThe node to(i + 1, j) 和 (i + 1, j + 1), so there are only 2 ways to go. Since we are dealing with the shortest, we can choose the minimum.Plus the value of the node itself.
    • dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
  • The boundary conditions
    • Through toi >= 0Just keep your eyes openIt starts in the second to last lineFrom down to upTraverse. Iterate over the last line triangle[i + 1]Will overflow

Writing implement

var minimumTotal = function(triangle) {
  / / sentence
  if (triangle.length === 1) {
    return triangle[0] [0]}// I = triangle. Length - 2,
  // Triangle [I + 1] overflows because we are traversing from the penultimate row
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      // You can change it in place
      triangle[i][j] += Math.min(
        triangle[i + 1][j], 
        triangle[i + 1][j + 1])}}return triangle[0] [0]};let triangle = [[2], [3.4], [6.5.7], [4.1.8.3]]
console.log(minimumTotal(triangle))
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference