1. Introduction

Today, I’m going to talk about dynamic programming, and the general form of dynamic programming is maximizing. In this kind of problem, there may be multiple solutions, but we want to find the optimal solution.

The dynamic programming algorithm is similar to the divide-and-conquer algorithm in that the basic idea is to decompose the problem into subproblems. Different from divide-and-conquer algorithm, there are too many subproblems that are suitable for dynamic programming algorithm to solve, and some subproblems will be repeated many times. If the results of the calculated subproblems are saved, a large number of repeated calculations can be avoided. This is the basic idea of dynamic programming algorithm.

The three steps to solve dynamic programming problems are generally as follows:

A. Find subproblems;

B. Define the state;

C. Column state (DP) equation;

This article will solve two dynamic programming problems, to understand the solution of dynamic programming problems, I hope to help you.

2. One-dimensional dynamic programming

I’ve divided the dynamic programming problem into one and two dimensions of difficulty, but let’s do one. In fact, the most important problem to solve dynamic programming is to list the equation of state, also known as DP equation. The first dynamic programming problem I came into contact with is the “stair climbing” problem. Next, let’s look at the “stair climbing” problem

This is a simple dynamic programming problem, so let’s start by listing its DP equation. Since you can climb one or two steps at a time, you can only climb n steps from n-1 or n-2 to n steps by the time you get to the NTH step. Assuming that there are f(n) ways to get to n steps, you have the following equation: F (n) = F (n-1) + f(n-2), f(1) =1 when n=1 or n=2; F (2)=2, so the equation of state is as follows:

Write the following code according to the equation of state:

public int  climbStairs(int n) {
    if(n==1||n==2) {return n;
    }
    return climbStairs(n-1)+climbStairs(n-2);
}
Copy the code

In fact, this is to use the divide-and-conquer method to solve, many repeated sub-problems are repeated to calculate, the next to optimize, the previous also said to save the calculated sub-problems, can avoid a lot of repeated calculation. Here, an array is used to store the results, and the DP equation is used to recurse the results.

public int climbStairs1(int n) {
    if(n==1||n==2) {return n;
    }
    int[] arr = new int[n+1];
    arr[0] = 1;
    arr[1] = 2;
    for (int i=3; i<arr.length; i++){/ / recurrence
        arr[i] = arr[i-1]+arr[i-2];
    }
    // Return the result
    return arr[n-1];
}
Copy the code

By using arrays for storage, the computation time complexity is greatly reduced.

3. Two-dimensional dynamic programming

So let’s look at dynamic programming in two dimensions, which is the DP equation for a two dimensional array, and let’s jump right into an example.

This problem I use two-dimensional array to solve, mainly want to explain the solution of dynamic programming in the three elements: “sub-problem”, “state”, “equation of state”.

First look for a quick question: the thief or not to steal the n house;

Let’s define the states: steal and do not steal are two states, which can be represented by 1 and 0 respectively.

The last DP equation is:

Math. Max (f(I,1) = f(i-1,0)+nums[I], f(i-1,0)) Math. Max (f(I,1) = f(i-1,0)+nums[I])

B. House I-1 must be stolen if house I-1 is not stolen. Maximum amount of money stolen: F (I,0) = F (i-1,1)

Next write the code:

public static int rob(int[] nums) {
    if(nums.length==0) {return 0;
    }
    int[][] dp = new int[nums.length][2];
    // Define first house to steal or not to steal
    dp[0] [1] = nums[0];
    dp[0] [0] = 0;
    for(int i=1; i<nums.length; i++){// I house stolen, maximum total amount
        dp[i][1] = Math.max(dp[i-1] [0]+nums[i],dp[i-1] [1]);
        // The I house is not stolen, the maximum total amount
        dp[i][0] = dp[i-1] [1];
    }
    // Return the maximum value
    return Math.max(dp[nums.length-1] [1],dp[nums.length-1] [0]);
}
Copy the code

In LeetCode, scrolling array is used in many problems, but two-dimensional array is used here to solve this problem. The main purpose is to understand how to define the state of the problem, and then list the state transition equation, which is the most important, and then optimize step by step, otherwise it will be very confusing to write the simplest way at the beginning.

conclusion

Three steps of dynamic programming: 1. Find subproblems; 2. Define the state; 3. Write the DP equation.

The most important thing is to write the DP equation. When a problem is not an obvious dynamic programming problem, you can consider the raised dimension to solve the problem, that is, write the two-dimensional equation of state. Well, that’s all for today’s dynamic programming. Have you failed?

Can see here are talents, your likes collection is my biggest power ~ also welcome to follow the public account “mountain master”, unlock more dry goods ~