Which problems can be solved by dynamic programming?

• count
  • How many ways to get to the lower right corner
  • How many ways to choose k numbers so that Sum is Sum
• Find the maximum and minimum value
  • The maximum number and number of paths from the upper left corner to the lower right corner
  • Longest rising sequence length
• Seeking existence
  • Will the first player win the stone game
  • Can you choose k numbers so that Sum is Sum

DP algorithm

The meaning of dynamic programming is to adopt a recursive (or divide and conquer) strategy,
Solve the overall approach by solving the sub problems of the big problem.

The core idea of dynamic programming is to divide the problem into several sub problems skillfully, and get the solution of the whole problem by calculating the sub problems.
The subproblem can be divided into more subproblems, so as to solve the required problem with a method similar to recursive iteration.

Dynamic programming component

• Determine status
• Transfer equation
• Initial condition (when f(0)) and boundary condition (array out of bounds)

Solution steps

• Determine status
  • When solving dynamic programming, you need to open an array. What does each element f[i] or f[i][j] of the array represent
• Two senses:
  • Last step
  • Subproblem

Coin Change

• The face values of the three coins are 2 yuan, 5 yuan and 7 yuan respectively. Each coin is enough
• It costs 27 yuan to buy a book
• How to pay with the least coin combination without change

Set status:
f(k) = how many coins do you use to spell K yuan
So:
f(27) = min{ f(27-2)+1，f(27-5)+1，f(27-7)+1 }

Recursive solution

int f(int X){
	if(X==0) return 0;
	int res = Integer.MAX_VALUE；
	if(X>=2) res = Math.min(f(X-2)+1,res);
	if(X>=5) res = Math.min(f(X-5)+1,res);
	if(X>=7) res = Math.min(f(X-7)+1,res);
	return res;
}

// The optimal strategy is k coins
//	dp[n] is the face value of the nth of the k coins
//	27 = dp[n] +dp[n-1]

dp solution

                           // {2,5,7}    27
    public static int DP06(int[] arr,int X){

        Determine status f[i]  : Minimum use f[i] One way is enough i element
        int dp[] = new int[X+1];
        dp[0] = 0;
        int n = arr.length;
        Transfer equation  f(27) = min{ f(27-2)+1，f(27-5)+1，f(27-7)+1 }
        int i ,j;
        for (j = 0; j < X; j++) {
            dp[j] = Integer.MAX_VALUE;
            for (i = 0; i < n; i++) {
                // dp[A] A may be negative
                // MAX_ The value + 1 result is negative in the computer
                if (j>arr[i]&&dp[j]!=Integer.MAX_VALUE){
                dp[j] = Math.min(dp[j-arr[i]],dp[j] );
                }
            }
        }
        if (dp[X] == Integer.MAX_VALUE) return -1;
        return dp[X];
    }

Fibonicci recursion

Recursive thought Fibonicci sequence

```

public static int Fibonacci(int n){
    // Recursive complexity O(2^n)
    if (n==1) return 1;
    if (n==2) return 2;
    return Fibonacci(n-1)+Fibonacci(n-2);
}

```

The DP policy Fibonicci sequence saves the calculated f(n)

```
 private static int[] arr = new int[50];

 public static int DP02(int n){
    if (n<=2) return 1;
    if (arr[n]!=0) return arr[n];
    else {
        arr[n] = Fibonacci(arr[n-1])+Fibonacci(n-2);
        return arr[n];
    }
 //The ARR array is initialized to 0, and arr[i] represents f(i),
// Judge whether arr[i] is 0 each time. If it is 0, it means it has not been calculated, and it is calculated recursively,
// If it is not 0, it means that it has been calculated, and it will be returned directly.
    ```

Robot walking grid

  /*
    *   The robot can only take one step down or right when walking in the grid
    *   Ask how many different ways to reach the bottom right grid
    *    D X X X X
    *    X X X X X
    *    X X X X P
    *
    *    Go from D(1,1) to P
    * */
    * 
    /*
    * thinking
    *      i-1,j  Downward i,j-1 to the right is the state transition equation
    * */

k1 l1 dp[0][1]+d[1][0] =1+1 = dp[1][1] = 2
k1 l2 02 + 11 = __ 02 should be reached in 2 steps, so the initial value like dp[0][index] dp[index][0] should be set for boundary conditions
k1 l3 03 + 12 = __

   public static int DP03(int i,int j){
   	int[][] dp = new int[i][j];
   	dp[0][0] = 0;
   	//        Initialize boundary
   	for(int k = 0; k < i; k++) {
            dp[0][k] = 1;
        }
    for (int k = 0; k < i; k++) {
            dp[k][0] = 1;
        }

   	for (int k = 1; k <= i; k++){
            for (int l = 1; l <= j; l++) {
                dp[k][l] =  dp[k-1][l]+dp[k][l-1];
            }
        }
    return dp[i][j];

}

The little frog jumped the steps

A frog can jump up one step or two steps at a time. Find out how many jumping methods the frog can jump up an n-step

Recursion and divide and conquer strategy

recursive algorithm

DP thought

Find the equation of state first:
f(n): the number of jump methods adjusted to n
f(n) = f(n-1) +f(n-2)

public int PD04(int n){
	int[] dp = new int[n]; 
	if(n<=2) return n;
	else{
		if(dp[n]!=0) return dp[n-1]+dp[n-2];
	   return dp[n];
	}
}

Longest subsequence

https://blog.csdn.net/hrn1216/article/details/51534607
https://blog.csdn.net/weixin_34476847/article/details/114030706