算法练习-DP动态规划

今天学习一下动态规划算法的应用与写法，准备机试进行时。

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用

1.解码方法

1.1题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:
输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

来源：https://leetcode-cn.com/problems/decode-ways/

1.2思路

这个和青蛙跳台阶差不多思路，都是动态规划问题。如果字符串第一位就是0，出错，那么返回0即可。如果当前位置是0，向前查找上一个位置是不是1或者2，如果不是，编码出错，返回0，如果是，当前的结果数量就是上一次的数量。如果当前位置是1-6之间的数字，我们可以去判断上一个位置是不是1或2，如果是，当前结果数量，就是上一次的加上上次的，因为本次可以有跳一个和跳两个两种。然后更新pre的值。

1.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int numDecodings(char * s){
    if (s[0] == '0' || s[0] == 0) 
        return 0;
    int pre = 1, curr = 1;//dp[-1] = dp[0] = 1
    for (int i = 1; s[i] != 0; i++) {
        int tmp = curr;
        if (s[i] == '0')
            if (s[i - 1] == '1' || s[i - 1] == '2') 
                curr = pre; //dp[i] = dp[i-2]
            else return 0; // error
        else if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6'))
            curr = curr + pre;  // dp[i] = dp[i-1] + dp[i-2]
        pre = tmp;  // next dp[i-2] = dp[i-1] 
    }
    return curr;
}

2.最长回文子串

2.1题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”

来源：https://leetcode-cn.com/problems/longest-palindromic-substring/

2.2思路

第一想法就是直接暴力搜索，分偶数长度和奇数长度回文字符串，直接尝试保存目前最长的回文子串即可。

2.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void helper(char *s, int N, int left, int right, int *start, int *len) {
    while (left >= 0 && right < N && s[left] == s[right])
        left--, right++;
    if (right - left - 1 > *len) {  // 如果找到更长的子串，保存其信息
        *start = left + 1;
        *len = right - left - 1;
    }
}
char * longestPalindrome(char * s){
    int N = strlen(s), start = 0, len = 0;  // N 字符串长度， start 子串起始位置， len 子串长度
    for (int i = 0; i < N; i++)     // 奇数长度的回文子串
        helper(s, N, i-1, i+1, &start, &len);
    for (int i = 0; i < N; i++)     // 偶数长度的回文子串
        helper(s, N, i, i+1, &start, &len);
    s[start + len] = '\0';          // 原地修改返回
    return s + start;
}

3.最大子序和

3.1题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

来源：https://leetcode-cn.com/problems/maximum-subarray/

3.2思路

动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 result
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 result的大小，将最大值置为result，遍历结束返回结果
时间复杂度：O(n)

3.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxSubArray(int* num, int numsSize){
    int i = 0,result = num[0],sum = 0;
    while(i<numsSize){
        if(sum >= 0){
            sum+=num[i];
            i++;
        }
        else{
            sum = num[i];
            i++;
        }
        if(sum>result){
            result = sum;
        }
    }
    return result;
}

4.不同路径

4.1题目描述

一个机器人位于一个 m x n 网格的左上角 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径？

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下

向右 -> 向下 -> 向右

向下 -> 向右 -> 向右

示例 2:
输入: m = 7, n = 3
输出: 28

4.2思路

第一个想到的直接计算阶乘即可，由于只能向右或者向下，那么根据数学知识可以很容易算出来结果，就是da。由于本章练习的是动态规划算法，所以还是用动态规划来写吧。

首先找到递推式，就是dp[i][j] = dp[i-1][j] + dp[i][j-1];

然后如果在最上面一行或者最左面，那么结果就是1。

4.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int uniquePaths(int m, int n){
    //动态创建一个二维路径答案表
    /*int **dp = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++) {
        dp[i] = (int *)malloc(sizeof(int) * m);
    }*/
    int dp[100][100];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0) {     //最上一行或者最左一列
                dp[i][j] = 1;
            }
            else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    return dp[n-1][m-1];//返回最后一个结果
}

5.不同路径升级版

5.1题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

5.2思路

和前面的差不多，只不过加了障碍，把有障碍的地方去掉，dp[i][j]=0，然后先把第一行和第一列初始化完毕，不能和上面的一样一起初始化了。

5.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int n = obstacleGridSize,m = *obstacleGridColSize;//n行，m列
    long int dp[100][100] = {0};

    if(obstacleGrid[0][0] == 1 || obstacleGrid[n-1][m-1] == 1 ){
        return 0;
    }
    for(int i = 0; i < n; i++){     //设置第一行的边界
        if(obstacleGrid[i][0] == 0){
            dp[i][0] = 1;
        }else{
            break;
        }
    }
    for(int i = 0; i < m; i++){     //设置第一列的边界
        if(obstacleGrid[0][i] == 0){
            dp[0][i] = 1;
        }else{
            break;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0);   //最上一行或者最左一列
            else if(obstacleGrid[i][j] == 1){
                dp[i][j] = 0;
            }
            else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    return dp[n-1][m-1];//返回最后一个结果
}

6.最小路径和

6.1题目描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源：https://leetcode-cn.com/problems/minimum-path-sum/

6.2思路

使用动态规划算法，dp数组记录该点到起始点的最短距离，边界时候单独处理，非边界取上一次计算的最小值加上本点的值即可。思路清晰代码也很简单。dp数组可以使用malloc动态分配即可，偷懒直接申请了一个挺大的空间。时间复杂度为遍历二维数组花费时间。

6.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define min(a,b)(a<b?a:b)

int minPathSum(int** grid, int gridSize, int* gridColSize){
    int m = gridSize,n = *gridColSize;
    int dp[1000][1000];

    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            if(i==0 && j==0 ){
                dp[i][j] = grid[i][j];
            }
            else if(i == 0){
                dp[i][j] = grid[i][j] + dp[i][j-1];
            }
            else if(j == 0){
                dp[i][j] = grid[i][j] + dp[i-1][j];
            }
            else{
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
            
        }
    }
    return dp[m-1][n-1];
}

7.编辑距离

7.1题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = “horse”, word2 = “ros”
输出: 3
解释:
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2:
输入: word1 = “intention”, word2 = “execution”
输出: 5
解释:
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

来源：https://leetcode-cn.com/problems/edit-distance/

7.2思路

动态规划：

dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1]到dp[i][j]需要进行替换操作，dp[i-1][j]到d[i][j]需要进行删除操作，dp[i][j-1] 到d[i][j]需要进行添加操作。

7.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define min(a,b) (a<b?a:b)

int minDistance(char * word1, char * word2){
    int n1 = strlen(word1);
    int n2 = strlen(word2);
    int dp[600][600];
    // 第一行初始化
    for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
    // 第一列初始化
    for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (word1[i -1] == word2[j - 1]) 
                dp[i][j] = dp[i - 1][j - 1];
            else 
                dp[i][j] = min(min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
        }
    }
    return dp[n1][n2];
}

8.买卖股票的最佳时机

8.1题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。

随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

来源：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii

8.2思路分析

每天我们其实是有四个状态，买入当前价格的股票，以当前价格的股票卖出。第二次买入股票，第二次卖出股票。

s0代表初始状态，初始时钱是 0。s1代表第一次买入后当前的钱，s2代表第一次卖出后当前的前，s3代表第二次买入后当前的钱，s4代表第二次卖出后当前的钱。然后我们只需要更新每天的这四个状态即可。

8.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define max(a,b) (a>b?a:b)

int maxProfit(int* prices, int pricesSize){
    if(pricesSize == 0) return 0;
    //进行初始化，第一天 s1 将股票买入，其他状态全部初始化为最小值
    int s1=-prices[0],s2=-2147483648,s3=-2147483648,s4=-2147483648;

    for(int i=1;i<pricesSize;++i) {            
        s1 = max(s1, -prices[i]); //买入价格更低的股
        s2 = max(s2, s1+prices[i]); //卖出当前股，或者不操作
        s3 = max(s3, s2-prices[i]); //第二次买入，或者不操作
        s4 = max(s4, s3+prices[i]); //第二次卖出，或者不操作
    }
    return max(0,s4);
}

9.三角形最小路径和

9.1题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

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

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

来源：https://leetcode-cn.com/problems/triangle

9.2思路

从倒数第二行开始计算每个数字到下一个节点的最小值，并加上当前节点值存入当前节点，最后triangle[0][0]中存储的就是最终的最短路径结果。

9.3代码

1
2
3
4
5
6
7
8
9
10
11
12
#define min(a,b) (a<b?a:b)

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){
    int i,j;
//自底向上
    for(i = triangleSize-2;i >= 0;i--){
        for(j = 0;j < triangleColSize[i];j++ ){
            triangle[i][j] = min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
        }
    }
    return triangle[0][0];
}

10.最大正方形

10.1题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

来源：https://leetcode-cn.com/problems/maximal-square

10.2思路分析

第一想法就是使用动态规划算法，将dp初始化为全零（不初始化直接用会导致测试时出错），如果当前点是1，然后dp[i][j] 取左侧、左上角、上侧最小值加一为当前点dp值，如果当前dp值大于maxqlen就将maxqlen置为当前dp值。最后返回maxqlen*maxqlen即可。中间最开始看错了输汝，以为矩阵里面是整形导致一直判断出错，要细心啊。

10.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    if(matrixSize == 0 || *matrixColSize ==  0){
        return 0;
    }
    int rows = matrixSize, cols = *matrixColSize;
    int dp[400][400] = {0};
    int maxsqlen = 0;
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            if (matrix[i-1][j-1] == '1'){
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                maxsqlen = max(maxsqlen, dp[i][j]);
            }
        }
    }
    return maxsqlen * maxsqlen;
}
#算法 #DP
算法练习-DP动态规划
https://chujian521.github.io/blog/2020/03/19/算法练习-DP动态规划/
作者
Encounter
发布于
2020年3月19日
许可协议