Dynamic programming

The modification process

Note: Dynamic programming is a technique that violently tries to reduce double counting.

1. Try to write the recursive version first (hardest)

2. Change to a version of mnemonic search using cache (time complexity of some problems and 3. Is the same as in.

3. Finally change to strict table structure dynamic programming

   1. Analyze the variation range of variable parameters, several variable parameters are several dimensional table

   2. Mark the end of the calculation

   3. According to the Base case of the Violent attempt version, mark the position that can be calculated without calculation.

   4. Look at the dependencies, push the other position.

   5. Determine the order of sequential calculations.

4. Further optimization

Related Topic 1

If I have N positions in a row, I’ll call them 1 to N, and N must be greater than or equal to 2. The robot starts out in position M (M must be one of 1 to N)

The robot can go left or right, if the robot comes to position 1, then it can only go right to position 2; If the robot goes to position N, then it can only go left to position N-1. How many ways can a robot take K steps to get to P, which must also be one of 1 to N? Given four arguments N, M, K, P, return the number of methods.

Example: N = 5, M = 2 and K = 3, P = 3

The arguments above represent all positions 1, 2, 3, 4, 5. The robot starts in position 2 and has to go through three steps to reach position 3. There are only three ways to go:

1) From 2 to 1, 1 to 2, 2 to 3

2) From 2 to 3, from 3 to 2, from 2 to 3

3) From 2 to 3, from 3 to 4, from 4 to 3

So return the number of methods 3.

Violent trial version

// N is the number of steps, M is the current position, K is the number of steps, Public static int ways1(int N, int M, int K) public static int ways1(int N, int M, int K, Int P) {/ / parameter is invalid directly returns 0 if (N < 2 | | K < 1 | | M < 1 | | M > N | | P < 1 | | P > N) {return 0; } return walk(N, M, K, P); return walk(N, M, K, P); } // N: position 1 ~ N, fixed parameter // cur: current position in cur, variable parameter // rest: there are still res steps left, variable parameter // P: The final target position is P, fixed argument I can only move between 1 and N, so I'm currently at cur, and after I do the REST step, Public static int walk(int N, int cur, int rest, int P) {// base case If (rest == 0){return cur == P? If (rest == 0){return cur == P? 1:0; } // If there is a rest step to go, and the current cur position is 1, then the current step can only go from 1 to 2. If (cur == 1){return walk(N, 2, reST-1, P); } // If there is a rest step to go, and the current cur position is N, then the current step can only go from N to n-1 // the next step is to go to n-1, If (cur == N){return walk(N, n-1, reST-1, P); } // If there is a rest step to go, and the current cur position is in the middle, then the current step can go left or right // After going left, the next step will be to go to cur+1, and the next step will be to go to cur+1, Return walk(N, cur + 1, REST-1, P) + walk(N, cur + 1, REST-1, P); }Copy the code

Complexity analysis: Because the whole process is equivalent to a tree, the depth of the tree is K, so the time complexity is O(2^K).

Memorized search version

When you write the violent attempt, then it’s all the same. Because in the process of sequential recursion, there will be a repeated calculation of a part that has already been computed by another recursive operation. So you can cache the computation.

public static int ways2(int N, int M, int K, Int P) {/ / parameter is invalid directly returns 0 if (N < 2 | | K < 1 | | M < 1 | | M > N | | P < 1 | | P > N) {return 0; Int [][] dp = new int[K + 1][N + 1]; int[] dp = new int[K + 1][N + 1]; For (int I = 0; i <= K; i++){ for (int j = 0; j < N; j++){ dp[i][j] = -1; Return walk2(N, M, K, P, dp); } public static int walk2(int N, int cur, int rest, int P, int[] dp) {if(dp[rest][cur]! = -1){ return dp[rest][cur]; If (rest == 0){dp[rest][cur] = cur == P? 1:0; return dp[rest][cur]; } if(cur == 1){ dp[rest][cur] = walk(N, 2, rest - 1, P); return dp[rest][cur]; } if (cur == N){ dp[rest][cur] = walk(N, N - 1, rest - 1, P); return dp[rest][cur]; } dp[rest][cur] = walk(N, cur + 1, rest -1, P) + walk(N, cur - 1, rest - 1, P); return dp[rest][cur]; }Copy the code

Time complexity: O(N * M) because each position is evaluated at most once.

Dynamic programming version of strict table structure

This step requires sorting out location dependencies.

public static int ways3(int N, int M, int K, Int P) {/ / parameter is invalid directly returns 0 if (N < 2 | | K < 1 | | M < 1 | | M > N | | P < 1 | | P > N) {return 0; Int [][] dp = new int[K + 1][N + 1]; int[] dp = new int[K + 1][N + 1]; dp[0][P] = 1; for (int i = 1; i <= K; I++){for (int j = 1; j <= N; j++){ if(j == 1){ dp[i][j] = dp[i - 1][2]; }else if(j == N){ dp[i][j] = dp[i - 1][N - 1]; }else{ dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } } } return dp[K][M]; }Copy the code

Time complexity: O(K x N).

Related Topic 2

Given an array arr, all values in arR are positive and may be repeated. Each value represents a currency with a face value, and the currency of each face value can be used any notes. Then an integer AIM is given, representing the amount of money to be found, and the minimum number of currencies that comprise AIM is found.

For example, arr=[5,2,3], aim=20.

Four fives make up twenty dollars, and all the other change schemes use more coins, so return four.

Violent trial version

// If arR [i.N-1] is used freely, you cannot get change at all. // If arR [I.N-1] is used freely, you cannot get change at all. Public static int process(int[] arr, int I, int rest) {// base case; // base case; If (I == arr.length){return rest == 0? 0:1; } // The minimum number of tickets, the initial value is -1, because no valid solution has been found; Rest for(int k = 0; rest for(int k = 0; rest for(int k = 0; k * arr[i] <= rest; K ++){// use k arr[I], Int next = process(arr, I +1, rest-k * arr[I]); rest-k * arr[I]; if (next ! = -1){// Only at the beginning is res == -1. res = res == -1 ? next + k : Math.min(res, next + k); } } return res; }Copy the code

Dynamic programming version of strict table structure

I’m not going to write mnemonic search, because we can just try to rewrite the strict table structure dynamic programming version by brute force.

Public static int minCoins1(int[] arr, public static int minCoins1(int[] arr, int aim) { if (arr == null || arr.length == 0 || aim < 0) { return -1; } // create table int N = arr.length; int[][] dp = new int[arr.length + 1][aim + 1]; for(int j = 1; j < aim + 1; j++){ dp[N][j] = -1; } for(int I = n-1; i >= 0; i--) { for (int rest = 0; rest <= aim; Rest ++) {// The original res becomes dp[I][rest] // returns the minimum number of coins used to reach the amount of money dp[I][rest] = -1; for (int k = 0; k * arr[i] <= rest; k++) { int next = dp[i + 1][rest - k * arr[i]]; if (next ! = -1) { dp[i][rest] = dp[i][rest] == -1 ? next + k : Math.min(dp[i][rest], next + k); } } } } return dp[0][aim]; }Copy the code

Related Topic 3

Given an integer array arr, a line of cards with different values is formed. Player A and player B take each card in turn, with player A taking first and player B second, but each player can only take the left or right card at A time. Player A and Player B are extremely smart. Please return the final winner’s score.

Arr =,2,100,4 [1]. At the beginning, player A can only take one or four. If player A takes away 1 at the beginning, the alignment becomes [2,100,4], then player B can take away 2 or 4, and then continue player A’s turn…

If player A takes away 4 at the beginning, the arrangement becomes [1,2,100], then player B can take away 1 or 100, and then it’s player A’s turn… Player A, being the smartest person in the world, is not going to take 4 first, because after 4 player B is going to take 100. So player A will take the 1 first, making the rank [2,100,4], and then player B will take the 100 either way. Player A wins with A score of 101. So return 101.

Arr = [1100, 2]. So player A starts off with A 1 or A 2, and player B, being the smartest person in the world, is going to take the 100. Player B wins with a score of 100. So return 100.

Violent trial version

/ / method one: // The first function is my first function, and the last function is my last function. Julio cruz and successful mutual nested get public static int win1 (int [] arr) {if (arr = = null | | arr. Length = = 0) {return 0; } return Math. Max (f(arr, 0, arr.length-1), s(arr, 0, arr.length-1)); } public static int f(int[] arr, int I, int j) {//base case, base case, base case If (I == j) {return arr[I]; } return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1)); } // It is my turn to play I + 1 ~ j or I ~ j-1, because it is the last hand function, // But I play first in that place, it is decided by the other side, Public static int s(int[] arr, int I, int j) {// Base case = 1; } return Math.min(f(arr, i + 1, j), f(arr, i, j - 1)); }Copy the code

Dynamic programming version of strict table structure

public static int win2(int[] arr) { if (arr == null || arr.length == 0) { return 0; } int[][] f = new int[arr.length][arr.length]; int[][] s = new int[arr.length][arr.length]; for (int j = 0; j < arr.length; J++) {/ / on the basis of violence from the base case to try / / s [] [] these parts are 0, so only need to f [] [] [j] [j] f = arr [j]; For (int I = j-1; int I = j-1; int I = j-1; i >= 0; i--) { f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]); s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]); } } return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]); } public static void main(String[] args) { int[] arr = { 1, 9, 1 }; System.out.println(win1(arr)); System.out.println(win2(arr)); }Copy the code

Related Topic 4 (3D Table)

You have a chess board. You put the entire board in the first quadrant, and the bottom left corner of the board is the position (0,0). So the entire board is a region of nine lines on the x-coordinate and ten lines on the y-coordinate. Given three arguments, x,y, k, return if the horse starts at (0,0) and has to take k steps, how many ways can it end up at (x,y)?

Violent trial version

public static int getWays(int x, int y, int step) { return process(x, y, step); } public static int process(int x, int y, int step) { Returns 0 if directly (x < 0 | | x > 8 | | y < 0 | | y > 9) {return 0; } if (step == 0) {return (x == 0 && y == 0)? 1:0; } // Since the horse runs on the sun, we can reach the point (x,y), Process (x + 1, y + 2, step-1) + process(x + 1, y + 2, step-1) + process(x + 2, y + 1) + process(x + 2, y + 1) + process(x + 2, y + 1) + process(x + 2, y + 1) + process(x + 2, y + 1) + process(x + 2, y + 1) step - 1) + process(x + 2, y - 1, step - 1) + process(x + 1, y - 2, step - 1) + process(x - 1, y - 2, step - 1) + process(x - 2, y - 1, step - 1) + process(x - 2, y + 1, step - 1); }Copy the code

Dynamic programming version of strict table structure

public static int dpWays(int x, int y, int step) { if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0) { return 0; Int [][][] dp = new int[9][10][step + 1]; dp[0][0][0] = 1; for (int h = 1; h <= step; h++) { for (int r = 0; r < 9; r++) { for (int c = 0; c < 10; c++) { dp[r][c][h] += getValue(dp, r - 1, c + 2, h - 1); dp[r][c][h] += getValue(dp, r + 1, c + 2, h - 1); dp[r][c][h] += getValue(dp, r + 2, c + 1, h - 1); dp[r][c][h] += getValue(dp, r + 2, c - 1, h - 1); dp[r][c][h] += getValue(dp, r + 1, c - 2, h - 1); dp[r][c][h] += getValue(dp, r - 1, c - 2, h - 1); dp[r][c][h] += getValue(dp, r - 2, c - 1, h - 1); dp[r][c][h] += getValue(dp, r - 2, c + 1, h - 1); } } } return dp[x][y][step]; } public static int getValue(int[][][] dp, int row, int col, int step) { Here only can manually determine the if (row < 0 | | row > 8 | | col < 0 | | col > 9) {return 0; } return dp[row][col][step]; }Copy the code

Related Topic 5

Given an array arr, all values in arR are positive and not repeated. Each value represents a denomination of currency, each denomination of currency can be used any note, and then given an integer AIM, representing the amount of money to find, find the number of methods to form AIM.

Violent trial version

Public static int way1(int[] arr, int aim){return process(arr, 0, aim); } public static int process(int[] arr, int index, int rest){//base case If (index == arr.length){return rest == 0? 1:0; } // arr[index] 0; Int ways = 0; for(int zhang = 0; arr[index] * zhang <= rest; zhang++){ ways += process(arr, index + 1, rest - arr[index] * zhang); } return ways; }Copy the code

Dynamic programming version of strict table structure

/ / aim is eventually to find change several public static int way2 (int [] arr, int aim) {if (arr = = null | | arr. Length = = 0) {return 0; } int N = arr.length; int[][] dp = new int[N + 1][aim + 1]; dp[N][0] = 1; for (int index = N - 1; index >= 0; index--){ for (int rest = 0; rest <= aim; rest++){ int ways = 0; for(int zhang = 0; arr[index] * zhang <= rest; zhang++){ ways += dp[index + 1][rest - arr[index] * zhang]; } dp[index][rest] = ways; } } return dp[0][aim]; }Copy the code

Strict table structure optimized version

public static int way3(int[] arr, int aim){ if(arr == null || arr.length == 0){ return 0; } int N = arr.length; int[][] dp = new int[N + 1][aim + 1]; dp[N][0] = 1; for (int index = N - 1; index >= 0; index--){ for (int rest = 0; rest <= aim; Rest ++){// Further optimization: slope optimization // The value of each position is (current row - one arr[index] cell value) + its following cell value dp[index][rest] = dp[index + 1][rest]; if (rest - arr[index] >= 0){ dp[index][rest] += dp[index][rest - arr[index]]; } } } return dp[0][aim]; }Copy the code

conclusion