算法练习——动态规划(一)

最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-path-sum

解题思路

  • 满足最优子结构,即最长路径的子路径也是对应顶点的最优值
  • 用一个二维数组存储对应坐标的最长路径值,注意第一行和第一列元素的值可以直接得出
  • 开始遍历,每一个元素判断从左边来和从上边来哪一个路径值最大,即去最大值作为该元素对应二维数组的值
  • 遍历完成,返回二维数组最后一个元素值即为所求

代码

class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        if(row==0&&col==0){
            return 0;
        }
        int[][] min = new int[row][col];
        min[0][0]=grid[0][0];
        for(int i=1;i<row;i++){
            min[i][0]=min[i-1][0]+grid[i][0];
        }
        for(int j=1;j<col;j++){
            min[0][j]=min[0][j-1]+grid[0][j];
        }
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                min[i][j]=Math.min(min[i-1][j]+grid[i][j],min[i][j-1]+grid[i][j]);
            }
        }
        return min[row-1][col-1];
    }
}

结果

在这里插入图片描述

时间复杂度分析

数组每一个元素遍历一次,故时间复杂度为O(m*n)

不同搜索二叉树

给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-binary-search-trees

解题思路

  • 满足最优子结构,即n个节点的二叉树种类对应的子二叉树种类也是最优值
  • 可以这样想:n个节点的二叉搜索树种类=(0个节点左子树种类n-1个节点右子树种类)+(1个节点左子树种类n-2个节点右子树种类)+…+(n-1个节点左子树种类*0个节点右子树种类)
  • 所以用一个长度为n的以为数组存储每个节点对应的二叉搜索树种类,设定n为0和1时 元素值为1,然后从2开始用上述迭代公式经行计算,直到计算到n即为所求

代码

class Solution {
    public int numTrees(int n) {
        if(n==0||n==1){
            return 1;
        }
        int[] num = new int[n+1];
        num[0] = num[1] = 1;
        for(int i=2;i<=n;i++){
            for(int k=0;k<i;k++){
                num[i]+=num[k]*num[i-1-k];
            }
        }
        return num[n];
    }
}

结果

在这里插入图片描述

时间复杂度分析

双重循环,时间复杂度为O(n^2)

最长重复子数组

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出:3
解释:
长度最长的公共子数组是 [3, 2, 1] 。

提示:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray

解题思路

  • 满足最优子结构,即最长的公共子字符串的子字符串也是对应元素最优值
  • 用一个二维数组存储A和B字符串每两个元素的映射关系,遍历A和B字符串,当A和B某一个字符相同时,就用前一个映射值+1作为此映射值,相当于在子结构上进行扩展。
  • 直至A和B字符串全部遍历完成,取出二维数组的最大元素值即为所求

代码

class Solution {
    public int findLength(int[] A, int[] B) {
        int findMax = 0;
        int row = A.length;
        int col = B.length;
        int[][] max = new int[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(A[i]==B[j]){
                    if(i==0||j==0){
                        max[i][j] = 1;
                    }
                    else{
                        max[i][j] = max[i-1][j-1]+1;
                    }
                    if(findMax<max[i][j]){
                        findMax = max[i][j];
                    }
                }
            }
        }
        return findMax;
    }
}

结果

在这里插入图片描述

时间复杂度分析

双重循环,时间复杂度为O(m*n)

分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。