# 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:

1. Status (dp array and meaning of subscript)
2. Recursive formula and cyclic structure
3. initialization
4. Return value

# Inscription

## 509. Fibonacci number 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;
dp = 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 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 = 1;
dp = 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

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 = cost;
dp = cost;
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

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] = 1;
for (int i = 0; i < n; i++) dp[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 = 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

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.length;
int[][] dp = new int[row][col];
for (int i = 0; i < row && obstacleGrid[i] == 0; i++) dp[i] = 1;
for (int j = 0; j < col && obstacleGrid[j] == 0; j++) dp[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.length;
int[][] dp = new int[row + 1][col + 1];
dp = 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

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;
dp = nums;
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

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 * 4, dp * 3, dp * 2, dp * 1. But there is no maximum here
dp = 1 * 1 = 1, dp = 1 * 2 = 2, maximum dp * 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 = 0
Return: dp[n]

```class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp = 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 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 = 1;
dp = 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];
}
}
```

Added by Redapple on Fri, 25 Feb 2022 15:35:16 +0200