62.不同路径

力扣题目链接

解题思路

1. 一个位置只能是左边的格子或者上面的格子到达，那么路径数就是左边格子的路径数加上上面格子的路径数

代码实现

int uniquePaths(int m, int n) {
    int dp[101][101] = {0};

    for (int i = 1; i <= n; i ++) {//赋值最上面的格子，因为只有左边的格子，所以只有一条路径
        dp[1][i] = 1;
    }

    for (int i = 1; i <= m; i ++) {//赋值最左边的格子，因为只有上面的格子，所以也只有一条路径
        dp[i][1] = 1;
    }

    for (int i = 2; i <= m; i ++) {
        for (int j = 2; j <= n; j ++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//由左边的格子的路径数加上上面格子的路径数
        }
    }

    return dp[m][n];
}

64.最小路径和

力扣题目链接

解题思路

1. 因为一个位置是由左边和上面的位置到的，因此当前位置的最小路径和也是由上面的最小路径和和左边的最小路径和构成的
2. 那么当前位置的最小路径和就是两个位置的最小路径和再加上当前位置的和

思路:暴力递归

int min(int a, int b) {
    return a <= b? a: b;
}

//返回从(0, 0)到(i ,j)位置的最小路径和
int dfs(int** grid, int n, int m, int i, int j) {
    if (i == 0 && j == 0) {//到了起始位置，那么最小路径和就是它本身
        return grid[0][0];
    }

    int up = 9999;//上面的最小路径和
    int left = 9999;//左边的最小路径和

   if (i - 1 >= 0 && j >= 0)  {//有上面的路
       up = dfs(grid, n, m, i - 1, j);
   }

   if (j - 1 >= 0 && i >= 0) {//有左边的路
       left = dfs(grid, n, m, i, j - 1);
   }

   return (min(up, left) == 9999? 0: min(up, min)) + grid[i][j];//取两个位置中最小的和当前位置的值相加
}

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int n = gridSize;//行数
    int m = *gridColSize;//列数

    return dfs(grid, n, m, n - 1, m - 1);
}

代码实现

int min(int a, int b) {
    return a <= b? a: b;
}

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

    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; i ++) {
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }
 
    for (int i = 1; i < n; i ++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

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

    return dp[n - 1][m - 1];
}

1143.最长公共子序列

力扣题目链接

解题思路

1. 因为是子序列，所以就是要或者不要，又因为有两个字符串，所以子序列就是要最后一个字符或者不要最后一个字符
2. 如果最后一个字符相等，那么先匹配

暴力递归

int max(int a, int b) {
    return a >= b? a: b;
}

//返回text1[0, len1 - 1]和text2[0, len2 - 1]中的最长公共子序列
int dfs(char* text1, char* text2, int len1, int len2) {
    if (len1 == 0 || len2 == 0) {//如果其中有一个长度为0，代表一个串没有字符了，那么最长公共子序列为0
        return 0;
    }

    int ans = 0;

    if (text1[len1 - 1] == text2[len2 - 1]) {//如果两个字符串的最后一个字符相等
        ans = 1 + dfs(text1, text2, len1 - 1, len2 - 1);//看前一个位置的最长公共子序列
    }
    else {//最后一个字符不相等
        ans = max(dfs(text1, text2, len1 - 1, len2), dfs(text1, text2, len1, len2 - 1));//要么要第最后一个字符串，要么不要最后一个字符串
    }

    return ans;
}

int longestCommonSubsequence(char* text1, char* text2) {
    return dfs(text1, text2, strlen(text1), strlen(text2));
}

代码实现

int max(int a, int b) {
    return a >= b? a: b;
}

//返回text1[0, len1 - 1]和text2[0, len2 - 1]中的最长公共子序列
int dfs(char* text1, char* text2, int len1, int len2) {
    if (len1 == 0 || len2 == 0) {//如果其中有一个长度为0，代表一个串没有字符了，那么最长公共子序列为0
        return 0;
    }

    int ans = 0;

    if (text1[len1 - 1] == text2[len2 - 1]) {//如果两个字符串的最后一个字符相等
        ans = 1 + dfs(text1, text2, len1 - 1, len2 - 1);//看前一个位置的最长公共子序列
    }
    else {//最后一个字符不相等
        ans = max(dfs(text1, text2, len1 - 1, len2), dfs(text1, text2, len1, len2 - 1));//要么要第最后一个字符串，要么不要最后一个字符串
    }

    return ans;
}

int longestCommonSubsequence(char* text1, char* text2) {
    int dp[1001][1001] = {0};
    int len1 = strlen(text1);
    int len2 = strlen(text2);

    for (int i = 1; i <= len1; i ++) {
        for (int j = 1; j <= len2; j ++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    return dp[len1][len2];
}