# Catalogue of series articles

I Array type problem solving method 1: dichotomy

II Array type problem solving method 2: Double finger needle method

III Array type problem solving method 3: sliding window

IV Array type problem solving method 4: simulation

V The basic operation and classic topics of the linked list

Vi Classic title of hash table

VII Classic title of string

VIII KMP of string

IX Solution: double pointer

X Classic title of stack and queue

Xi top-K problem in stack and queue

XII The first, middle and last order traversal of binary tree

XIII Sequence traversal of binary tree and related topics

XIV Binary tree part of binary tree attributes related topics

XV Modification and construction of binary tree in binary tree chapter

XVI Properties of binary search tree

XVII The problem of common ancestor in binary tree discourse

XVIII Modification and construction of binary search tree in binary tree chapter

XIX Combinatorial problem of backtracking algorithm

XX The algorithm of the whole subset

XXI Introduction to greedy algorithm

XXII Advanced problem of greedy algorithm

Updating

# preface

The question brushing route comes from: Code Capriccio

Every state in dynamic programming must be derived from the previous state, such as frog jumping step, and the nth step jumps up from N-1 or N-2 step.

Problem solving steps:

- Status (dp array and meaning of subscript)
- Recursive formula and cyclic structure
- initialization
- Return value

# Inscription

## 509. Fibonacci number

Leetcode link

Solution:

Method 1: recursion

class Solution { public int fib(int n) { if (n == 0 || n == 1) return n; return fib(n - 1) + fib(n - 2); } }

Mode 2: dynamic programming

class Solution { public int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }

Space optimization:

class Solution { public int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; int a = 0; int b = 1; int res = 0; for (int i = 2; i <= n; i++) { res = a + b; a = b; b = res; } return res; } }

## 70. Climb stairs

Leetcode link

Solution:

The nth floor stairs jump up from the N - 1 or N - 2 floor

dp array

class Solution { public int climbStairs(int n) { if (n == 1) return 1; int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }

## 746. Use the minimum cost to climb stairs

Leetcode link

Give you an integer array cost, where cost[i] is the cost of climbing up the ith step of the stairs. Once you pay this fee, you can choose to climb up one or two steps.

You can choose to climb the stairs from the steps with subscript 0 or subscript 1. Please calculate and return the minimum cost to reach the top of the stairs.

Solution:

class Solution { public int minCostClimbingStairs(int[] cost) { int len = cost.length; int[] dp = new int[len]; dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < len; i++) { dp[i] = Math.min(dp[i - 1], dp[i - 2]) +cost[i]; } return Math.min(dp[len - 1], dp[len - 2]); } }

## 62. Different paths

Leetcode link

A robot is located in the upper left corner of an m x n grid (the starting point is marked "Start" in the figure below). The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "Finish" in the figure below). How many different paths are there altogether?

Solution:

Status (i, j): number of paths from (0, 0) to (i, j)

Equation of state: F(i,j) = F(i-1,j) + F(i,j-1)

Initial state: F(0,0) = F(0,j) = F(i,0) = 1

class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) dp[i][0] = 1; for (int i = 0; i < n; i++) dp[0][i] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n- 1]; } }

Optimization:

Status (i,j): number of paths from (0, 0) to (i,j)

Equation of state: F(i,j) = F(i-1,j) + F(i,j-1)

Initial state: F(0,j) = F(i,0) = 0, F(0,1) = 1 or F(1,0) = 1

Return result: F(row,col)

class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m + 1][n + 1]; dp[0][1] = 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m][n]; } }

## 63. Different paths II

Leetcode link

A robot is located in the upper left corner of an m x n grid (the starting point is marked "Start" in the figure below). The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "Finish" in the figure below). Now consider that there are obstacles in the grid. So how many different paths will there be from the upper left corner to the lower right corner? The obstacles and empty positions in the grid are represented by 1 and 0 respectively.

Solution:

As above, change the initial state. When the first row and the first column encounter stones, the back will also be initialized to 0, and only the place with stones in the middle area will be 0

class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int row = obstacleGrid.length; int col = obstacleGrid[0].length; int[][] dp = new int[row][col]; for (int i = 0; i < row && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1; for (int j = 0; j < col && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1; for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { if (obstacleGrid[i][j] == 0) { dp[i][j] = dp[i - 1][j] + dp[i][j -1]; } else { dp[i][j] = 0; } } } return dp[row - 1][col - 1]; } }

Optimization:

class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int row = obstacleGrid.length; int col = obstacleGrid[0].length; int[][] dp = new int[row + 1][col + 1]; dp[0][1] = 1; for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { if (obstacleGrid[i - 1][j - 1] == 1) { dp[i][j] = 0; }else { dp[i][j] = dp[i][j - 1] + dp[i -1][j]; } } } return dp[row][col]; } }

## 53. Maximum subarray and

Leetcode link

Give you an integer array nums. Please find a continuous sub array with the largest sum (the sub array contains at least one element) and return its maximum sum. A subarray is a contiguous part of an array.

Solution:

Status dp[i]: calculate the sum of the longest continuous subarray at position i

Equation of state: DP [i] = math max(dp[i - 1] + nums[i], nums[i])

Return value: maxSum during traversal

class Solution { public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; int maxSum = nums[0]; dp[0] = nums[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); maxSum = Math.max(dp[i], maxSum); } return maxSum; } }

## 343. Integer splitting

Leetcode link

Given a positive integer n, split it into the sum of K positive integers (k > = 2) and maximize the product of these integers. Returns the maximum product you can obtain.

Solution:

Example: 5 can be decomposed into 1 + 4, 2 + 3, 3 + 2 and 4 + 1

dp[1] * 4, dp[2] * 3, dp[3] * 2, dp[4] * 1. But there is no maximum here

dp[2] = 1 * 1 = 1, dp[3] = 1 * 2 = 2, maximum dp[3] * 2 = 4

The largest is 6:5 = 2 + 3, 2 * 3 = 6

For larger numbers, the recursive formula is satisfied, so the recursive formula includes: math max(dp[j] * (i - j), j * (i - j))

Status dp[i]: split maximum product of integer I

Equation of state: math max(dp[i], Math.max(dp[j] * (i - j), j * (i - j)));

It can also be understood that j * (i - j) simply divides an integer into two numbers and multiplies, while j * dp[i - j] is divided into two or more numbers and multiplies.

Initialization: because k > = 2, dp[2] = 0

Return: dp[n]

class Solution { public int integerBreak(int n) { int[] dp = new int[n + 1]; dp[2] = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j <= i - 1; j++) { dp[i] = Math.max(dp[i], Math.max(dp[j] * (i - j), j * (i - j))); } } return dp[n]; } }

## 96. Different binary search trees

Leetcode link

Solution:

i is expressed as n

J means that j is the root node

For example, when i = 3, j is 1, 2 and 3 respectively

class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j- 1] * dp[i - j]; } } return dp[n]; } }