120. The minimum path of a triangle and ( secondary )

subject ：

Given a triangle , Find the smallest sum from the top down . Each step can only move to adjacent nodes in the next row .

 for example , Given triangle ：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
 The minimum path sum from the top down is zero  11（ namely ,2 + 3 + 5 + 1 = 11）.

The triangle is represented by a two-dimensional array

[
	[2],
	[3, 4],
	[6, 5, 7],
	[4, 1, 8, 33]
]

It can be seen that , To know the shortest path, you need to know the shortest path from the top to each layer .
That is to say, from [2] The first floor starts , The shortest path of the first layer is 2, Next, you need to know the second layer [3, 4] The minimum value of , With the shortest path of the first layer 2 Add up , Is the shortest path after the end of the second floor .
Traverse it in turn .

But it should be noted that , The title stipulates that each step can only move to the adjacent nodes in the next row , This means that only the direction of the triangle “ The lower left ” and “ The lower right ” Fang Qianjin .

Therefore, according to the steps of dynamic programming ：

• Divide the problem into subproblems to get the optimal solution
  What we need to find is the shortest path from the vertex to the whole , So we get the shortest path layer by layer
• We set the state transition equation , Use a two-dimensional array dp To store the sum of paths
  According to the title, we can obtain the state transition equation
  dp[i][j] = min( dp[i+1][j] , dp[i+1][j+1] ) + path[i][j]
• Judge boundary condition , End when you reach the bottom or right of the triangle

If you want to solve the shortest path from top to bottom , In addition to judging the boundary conditions , The final shortest path can only be obtained by judging the minimum value of the bottom . Therefore, solving the problem from bottom to top will save a lot of problems .

class Solution {
    
public:
    int minimumTotal(vector<vector<int>>& triangle) {
    
        if(triangle.empty()){
    
            return 0;
        }
        int row = triangle.size();          // row of the triangle
        int column = triangle.back().size();    // Size of the last row in the triangle
        vector<vector<int>> dp(row+1, vector<int>(column+1, 0));
        // Adding another row is designed to caculate the last row of dp. 
        for(int i = row - 1; i >= 0; --i){
    
            for(int j = 0; j < triangle[i].size(); j++){
    
                // state transition equation
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }
};

64. Minimum path sum ( secondary )

subject ：

Given a... That contains a nonnegative integer m x n grid , Please find a path from the top left corner to the bottom right corner , Make the sum of the numbers on the path the smallest .

explain ： You can only move down or right one step at a time .

 Example :

 Input :
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
 Output : 7
 explain :  Because the path  1→3→1→1→1  The sum of is the smallest .

Typical dynamic programming problems .
First of all, according to the meaning of the title , The grid consists of a two-dimensional array m×n constitute , Therefore, we can get that the path starts in the upper left corner, that is, the upper left corner of the two-dimensional array [0][0] Location , By moving to the right or down, the final destination is [m][n] The point of , Now let's minimize the sum of the paths , We need to use dynamic programming .

According to the general steps of dynamic programming ：

• Analyze the problem and find the subproblem ; We will find the final shortest path as the final problem , Find the shortest path of the stage as the subproblem
• The boundary conditions ; When traversing the right and lower boundaries of a two-dimensional array , The solving process ends
• State transition equation ; From the upper left corner to the lower right corner
  dp[i][j] += min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
• solve

But when we use dp Array to store the shortest path results , When i = 0, j = 0, There will be boundary problems . Observation shows that the first line can only be directed to Right Forward , The first column can only be directed to Next Forward , So let's calculate the result in advance in the first row and the first column , At this time, the boundary situation does not need to be considered .

When the loop ends , return dp[m][n] , The shortest path .

class Solution {
    
public:
    int minPathSum(vector<vector<int>>& grid) {
    
        if(grid.empty()){
    
            return 0;
        }
        int row = grid.size();      
        int column = grid.back().size();
        vector<vector<int>> dp(row, vector<int>(column, 0));
        dp[0][0] = grid[0][0];
        for(int i = 1; i < row; i++){
           // Caculate result of the first column
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1; j < column; j++){
        // Caculate result of the first row
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        for(int i = 1; i < row; i++){
    
            for(int j = 1; j < column; j++){
    
                // state transition equation
                dp[i][j] += min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[row-1][column-1];
    }
};

198. raid homes and plunder houses ( Simple )

subject ：

You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Calculate if you don't touch the alarm , The maximum amount that can be stolen .

 Example  1:

 Input : [1,2,3,1]
 Output : 4
 explain :  Steal  1  House No  ( amount of money  = 1) , And then steal  3  House No  ( amount of money  = 3).
      Maximum amount stolen  = 1 + 3 = 4 .
 Example  2:

 Input : [2,7,9,3,1]
 Output : 12
 explain :  Steal  1  House No  ( amount of money  = 2),  Steal  3  House No  ( amount of money  = 9), Then steal  5  House No  ( amount of money  = 1).
      Maximum amount stolen  = 2 + 9 + 1 = 12 .

A very classic dynamic programming problem .
Simplify the topic according to the meaning of the topic , When traversing an array, you cannot sum two consecutive numbers , Finally, the sum of the maximum numbers that can be obtained without violating this condition .

According to the general steps of dynamic programming ：

• To analyze problems , Partition subproblem ; Find the sum of the final numbers as the final result , Find the sum of the maximum number of stages as the subproblem
• The boundary conditions ; You cannot sum two consecutive numbers , When the traversal ends or there is no next number to add
• State transition equation ;
  To get the current maximum number and , You need to know the sum of the current number and the previous second number , Compare the sum of this number with the sum of the first number before , The largest one is the current maximum number and .
  dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
• End of traversal

To make the equation of state work , Must start from the number i = 2 Start , So for unnecessary trouble , take dp The length of the array is nums Add one to the length of , take **dp[0]** Set to 0,dp[1] Set to nums[0] .

class Solution {
    
public:
    int rob(vector<int>& nums) {
    
        if(!nums.size()){
    
            return 0;
        }
        if(nums.size() == 1){
    
            return nums[0];
        }
        int len = nums.size();
        vector<int> dp(len+1, 0);		// len + 1
        dp[0] = 0, dp[1] = nums[0];		// Initialization
        for(int i = 2; i <= len; i++){
    
        	// state transition equation
            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]) ;
        }

        return dp[len];
    }
};

62. Different paths ( secondary )

subject ：

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish”）.

Ask how many different paths there are in total ？

 Example  1:

 Input : m = 3, n = 2
 Output : 3
 explain :
 From the top left corner , All in all  3  Path to the bottom right .
1.  towards the right  ->  towards the right  ->  Down 
2.  towards the right  ->  Down  ->  towards the right 
3.  Down  ->  towards the right  ->  towards the right 
 Example  2:

 Input : m = 7, n = 3
 Output : 28

Tongyu Minimum path sum The same problem solving steps , Just for dp The initialization and state transition equations are slightly modified .

According to the problem-solving steps of dynamic programming ：

• To analyze problems , Divide the problem into subproblems ; Request from point (0,0) Get a point (m-1,n-1) All paths and , You need to know from (0,0) To (0,1), (1,0) …… The path and , Then add the path and to the point (m-1, n-1) The path and
• The boundary conditions ; Initialize the first row and first column , End of array boundary reached
• State transition equation ; It's not hard to see. , Robot intelligence moves right and down , So reference Minimum path sum The state transfer equation can be obtained
  dp[i][j] = dp[i-1][j] + dp[i][j-1]
• End of traversal

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        if(!m || !n){
    
            return 1;
        }
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++){
         // Initialization of the first column
            dp[i][0] = 1; 
        }
        for(int j = 0; j < n; j++){
         // Initialization of the first row
            dp[0][j] = 1;
        }
        for(int i = 1; i < m; i++){
    
            for(int j = 1; j < n; j++){
    
                // state transition equation
                dp[i][j] += dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};