Example 1: Continuous series (simple interview question 16.17)

Title link: Force bucklehttps://leetcode-cn.com/problems/contiguous-sequence-lcci/

Title: Given an array of integers, find the largest continuous sequence of sums and return the sum.

Example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6

Interpretation: The sum of consecutive subarrays [4, -1, 2, 1] is maximum, which is 6

Topic Analysis: Use a number to dynamically store the sum of consecutive numbers and then find the maximum value.

Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int ans = 0, res = nums[0];//Ansstores the sum of consecutive values, and res stores the maximum
        for(int i = 0; i < n; i ++)
        {
            ans = max(ans + nums[i], nums[i]); //Sum used to store continuous values
            res = max(res, ans);
        }
        return res;
    }
};

Example 2: Minimum path and (force button 64 medium)

Title link: Force bucklehttps://leetcode-cn.com/problems/minimum-path-sum/

Title: Given an m-X-n grid containing non-negative numbers, find a path from the upper left corner to the lower right corner so that the sum of the numbers of the paths is minimal. (Note: You can only move down or right one step at a time)

Example 1:

Input: grid = [[1, 2, 1], [1, 5, 1], [4, 2, 1]]

Output: 7

Explanation: Because the sum of paths 1->3->1->1->1 is the smallest

Example 2:

Input: grid = [[1, 2, 3], [4, 5, 6]]

Output: 12

Topic Analysis: A two-dimensional array is used to store the minimum path sum for each point. The minimum path for the first row and column is the sum of the row or the beginning of the column to the point, the minimum path to (i, j) point, and the path for that point + to (i - 1, j) and the minimum value in (i, j - 1).

Code:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> ans(n, vector<int>(m)); //Path used to record to (i, j)
        ans[0][0] = grid[0][0];
        for(int i = 1; i < n; i ++) ans[i][0] = ans[i - 1][0] + grid[i][0];
        for(int i = 1; i < m; i ++) ans[0][i] = ans[0][i - 1] + grid[0][i];
        for(int i = 1; i < n; i ++)
        {
            for(int j = 1; j < m; j ++)
                ans[i][j] = min(ans[i][j - 1], ans[i - 1][j]) + grid[i][j];
        }
        return ans[n - 1][m - 1];
    }
};

Example 3: Paint house (Swordfinger Offer II 91 Medium)

Title link: Force bucklehttps://leetcode-cn.com/problems/JEj789/

Title: If you have a row of houses with N in total, each house can be painted in one of three colors: red, blue or green, you need to paint all the houses and make the two adjacent houses not the same color. Of course, the cost of painting a house in different colors varies because the price of different colors in the market varies. The cost of painting each house in a different color is represented by a positive integer matrix costs of n X 3. For example, costs[0][0] represents the cost of painting house 0 red; costs[1][0] represents the cost of painting House 1 green, and so on. Please calculate the minimum cost of painting all the houses.

Example 1:

Input: costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]

Output: 10

Interpretation: Paint house 0 in blue, house 1 in green, and house 2 in blue. Minimum cost: 2 + 5 + 3 = 10.

  

Example 2:

Input: costs = [[7, 6, 2]]

Output: 2

Tip:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

Title Analysis: Use a two-dimensional array to store the minimum cost of painting house I I with color jth and each house has a different color (dp[i][j]) =the cost of painting house I I with color jth (costs[i][j]) +the minimum cost of painting house I I-1 with one of the other two colors (min (dp[i-1][], dp[i-1][])), Find the minimum value in dp[n-1] at last.

Code

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n, vector<int>(3)); //dp[i][j] is used to record house number I being painted J (red, blue, green)
        for(int i = 0; i < 3; i ++)
            dp[0][i] = costs[0][i];
        for(int i = 1; i < n; i ++)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
        }
        return min(dp[n - 1][0], min(dp[n - 1][2], dp[n - 1][1]));
    }
};

Summary:

The core of dynamic programming is to find the before-and-after relationships (mathematical relationships) and define some initialized values.