算法题总结(十六)—— 动态规划(上)

动态规划

动态规划理论基础

什么是动态规划

动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。

动态规划的解题步骤

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

动态规划应该如何debug

找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导的!

做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

509、斐波那契数

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。

动规五部曲:

这里我们要用一个一维dp数组来保存递归的结果

1、确定dp数组以及下标的含义

dp[i]的定义为:第i个数的斐波那契数值是dp[i]

2、确定递推公式

为什么这是一道非常简单的入门题目呢?

因为题目已经把递推公式直接给我们了:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3、dp数组如何初始化

题目中把如何初始化也直接给我们了,如下:

dp[0] = 0;
dp[1] = 1;

4、确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的

5、举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是一致的。

//非压缩状态的版本
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;             
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++){
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }
}

70、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

1、确定dp数组以及下标的含义

dp[i]: 爬到第i层楼梯,有dp[i]种方法

2、确定递推公式

首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!

所以dp[i] = dp[i - 1] + dp[i - 2] 。

3、初始化

重要:

关于dp[0]的定义,由于dp[0]没有意义,所以从dp[1]开始,初始化dp[1]=1, dp[2]=2

class Solution {
    public int climbStairs(int n) {
        if(n==1||n==2)
            return n;

        int[] dp =new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];

    }
}

爬楼梯扩展

这道题目还可以继续深化,就是一步一个台阶,两个台阶,三个台阶,直到 m个台阶,有多少种方法爬到n阶楼顶。这又有难度了,这其实是一个完全背包问题。

当做完全背包的求和问题:因为是排列问题,所以先遍历容量,在遍历物品,因为是完全背包,所以内循环小从小到大,然后容量大于物品时,dp[i]+=dp[i-j];

class Solution{
    public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) { // 把m换成2,就可以AC爬楼梯这道题
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

746、使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

示例 2:

输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。

1、确定dp数组以及下标的含义

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

2、确定递推公式

可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?

一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

3、dp数组如何初始化

题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。

所以初始化 dp[0] = 0,dp[1] = 0;

4、确定遍历顺序:从前向后

5、模拟

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];

        // 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0
        dp[0] = 0;
        dp[1] = 0;

        // 计算到达每一层台阶的最小费用
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[len];
    }
}

62、不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28
public static int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    //初始化
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }

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

63、不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

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

对比62、不同路径,如果有障碍,就是把对应的标记dp标记为0就可以。在初始化的时候,如果遇到了障碍,则后面的也都初始化为0

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        //如果在起点或终点出现了障碍,直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }

        for (int i = 0; i < m; i++) {
            if(obstacleGrid[0][0]==0)
                dp[i][0] = 1;
            else
                break;  //遇到障碍直接结束,后面都初始化为0
        }
        for (int j = 0; j < n; j++) {
            if(obstacleGrid[0][j] == 0)
                dp[0][j] = 1;
            else
                break;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
            }
        }
        return dp[m - 1][n - 1];
    }
}

64、最小路径和

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

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

示例 1:

输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

示例 2:

输入:grid = [[1,2,3],[4,5,6]]
输出:12
class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int dp[][] =new int[m][n];  //表示最小的数字总和
        //初始化
        int sum=0;
        for(int i=0;i<m;i++)
        {
            sum+=grid[i][0];
            dp[i][0]=sum;
        }
        sum=0;
        for(int j=0;j<n;j++)
        {
            sum+=grid[0][j];
            dp[0][j]=sum;
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];

    }
}

343、整数拆分

给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

返回 你可以获得的最大乘积

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp =new int[n+1];
        //初始化,dp[0]和dp[1]的初始化没有意义,因为0,1都无法拆开
        dp[2]=1;

        for(int i=3;i<=n;i++)
        {
            //只需要到i/2即可,因为拆成大小相近的数才能使乘积最大。
            //即拆分一个数n 使之乘积最大,那么一定是拆分成m个近似相同的子数相乘才是最大的
            for(int j=1;j<=i/2;j++)
            {
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));   //一定不要忘dp[i]也要比较
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ,再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];

    }
}

96、不同的二叉搜索树

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

其实就是求n个结点,构成的二叉树的数目,有多少个。因为二叉树确定了,只需要填数字,就变为二叉搜索树。

dp[i]就是i个结点能构成的二叉树的数目

递推公式:

选取一个作为根结点,剩下的i-1个结点,进行分配,左节点的个数依次是0到i-1,右节点的个数是i-1到0;

即j是从1到i

dp[i]+=dp[j-1]*dp[i-j];

class Solution {
    public int numTrees(int n) {
        //实际上就是求n个结点能构成的二叉树的数目
        //因为我们求出后只需填数字就可以

        //定义为 i个结点能组成的二叉树的数目
        int[] dp =new int[n+1];
        dp[0]=1; //为了让后面相乘不为0
        dp[1]=1;

        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                //一共i个结点,选取1个做根,然后剩下的i-1个分到左右子树
                //即左子树结点依次为:0到i-1个
                //右子树的结点为i-1到0
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];


    }
}

01背包理论基础

重点:01背包和完全背包

1、确定dp数组以及下标的含义

使用二维数组,即dp[i] [j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

2、确定递推公式

那么可以有两个方向推出来,即放物品i和不放物品i

所以递归公式:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

3、初始化

如果背包容量j为0的话,即dp[i] [0],无论是选取哪些物品,背包价值总和一定为0

由递推公式可知需要初始化dp[0],

那么很明显当 j < weight[0]的时候,dp[0] [j] 应该是 0,因为背包容量比编号0的物品重量还小。

当j >= weight[0]时,dp[0] [j] 应该是value[0],因为背包容量放足够放编号0物品。

4、遍历顺序

因为从递推公式可以看出,dp依赖的是左上角以及上方的数值,所以一行一行遍历和一列一列遍历都是可以的,所以先遍历物品还是先遍历背包都是可以的!

public class BagProblem {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp数组,其余的都是0
        // 创建数组后,其中默认的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    /**
                     * 当前背包的容量都没有当前物品i大的时候,是不放物品i的
                     * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                     */
                    dp[i][j] = dp[i-1][j];
                } else {
                    /**
                     * 当前背包的容量可以放下物品i
                     * 那么此时分两种情况:
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下,哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

01背包理论基础(滚动数组)

使用一维数组

1、确定dp数组的定义

在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。

2、递推公式

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3、初始化

都初始化为0,如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,如果题目给的价值有负数,那么非0下标就要初始化为负无穷。

4、遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }	
}

01背包的一维数组,背包为什么要倒叙遍历?

倒序遍历的原因是,本质上还是一个对二维数组的遍历,并且右下角的值依赖上一层左上角的值,因此需要保证左边的值仍然是上一层的,从右向左覆盖。即二维数组,从上到下 是从右向左遍历的。

即只用倒序遍历,才能使用一维数组模拟二维数组。

背包倒序遍历是为了保证每个物品i只被放入一次!多重背包的话是从小到大的遍历!,因为计算dp[j]的时候,是用到dp[j - weight[i]],如果正序遍历,那每一个物品会被放入多次!

不能先遍历背包在遍历物品,因为一维数组,背包容量一定是要倒序遍历,因为只有倒序遍历才能利用一维数组,如果遍历背包容量放在上一层,那么对每个背包dp[j]就只会放入一个物品,即:背包里只放入了一个物品。

public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWight = 4;
    testWeightBagProblem(weight, value, bagWight);
}

public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
    int wLen = weight.length;
    //定义dp数组:dp[j]表示背包容量为j时,能获得的最大价值
    int[] dp = new int[bagWeight + 1];
    //遍历顺序:先遍历物品,再遍历背包容量
    for (int i = 0; i < wLen; i++){
        for (int j = bagWeight; j >= weight[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    //打印dp数组
    for (int j = 0; j <= bagWeight; j++){
        System.out.print(dp[j] + " ");
    }
}

416、分割等和子集

给你一个 只包含正整数非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

转化为01背包问题:

  • 背包的容量为sum / 2,即判断能否把背包装满即可
  • 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
  • 背包如果正好装满,说明找到了总和为 sum / 2 的子集, 即dp[target]==target,因为装的时候是尽可能的装的最大
  • 背包中每一个元素是不可重复放入,说明是01背包问题。
class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        int n=nums.length;
        for(int num:nums)
        {
            sum+=num;
        }
        if(sum%2==1)
            return false;
        int target=sum/2;   //即背包的总容量
        int[] dp=new int[target+1];     //dp数组是一直到target
        for(int i=0;i<n;i++)
        {
            for(int j=target;j>=nums[i];j--)
            {
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);  
            }
        }
        //因为每次都是尽可能的装到最大,即尽可能的接近target,所以只需要判断最后的是否等于target
        return dp[target]==target;
    }
}

1049、最后一块石头的重量 II

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

  • 如果 x == y,那么两块石头都会被完全粉碎;
  • 如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。

最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。

示例 1:

输入:stones = [2,7,4,1,8,1]
输出:1
解释:
组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。

本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了

所以和上一题基本一样,最后dp[target]里是容量为target的背包所能背的最大重量。

那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int stone:stones)
        {
            sum+=stone;
        }
        int target=sum/2;  //容量为总和的一半,尽可能装到最大。
        int[] dp=new int[target+1];
        for(int i=0;i<stones.length;i++)
        {
            for(int j=target;j>=stones[i];j--)
            {
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];

    }
}

494、目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式

  • 例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

这道题目咋眼一看和动态规划背包啥的也没啥关系,本质上还是把数分为两部分

本题要如何使表达式结果为target,

既然为target,那么就一定有 left组合 - right组合 = target。

left + right = sum,而sum是固定的。right = sum - left

公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2 。

target是固定的,sum是固定的,left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

此时问题就转化为,装满容量为left的背包,有几种方法

注意之前的都是求装满背包的最大容量是多少。

因为 left = (target + sum)/2 ,所以 (target + sum)如果是奇数的话,是无解的,另外,如果target的绝对值大于sum的绝对值也是无解的。

1、确定dp数组以及下标的含义

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

注意递推公式的含义是有多少种方法!

2、递推公式,组合类问题的递推公式是什么样的呢?

dp[j] += dp[j - nums[i]]

注意:求装满背包有几种方法类似的题目,递推公式基本都是这样的

例如:dp[j],j 为5,

  • 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
  • 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
  • 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
  • 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
  • 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - nums[i]] 累加起来。

3、初始化

从递推公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递推结果将都是0。

dp[j]其他下标对应的数值也应该初始化为0,从递推公式也可以看出,dp[j]要保证是0的初始值,才能正确的由dp[j - nums[i]]推导出来。

4、遍历顺序

nums放在外循环,target在内循环,且内循环倒序。

即外循环遍历的时候,就相当于用0到i的物品来装容量为j的背包,j要倒序来装。 理解下图!

5、举例子

输入:nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {

        int sum=0;
        for(int num:nums)
        {
            sum+=num;
        }
        //(target + sum)如果是奇数的话,是无解的
        if((sum+target)%2==1)
            return 0;
        if(Math.abs(target)>sum)
            return 0;
        int size = (target+sum)/2;  //size不可能为负的,相当于背包的容量
        int[] dp =new int[size+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++)
        {
            for(int j=size;j>=nums[i];j--)
            {
                dp[j]+=dp[j-nums[i]];   //可以把dp[j] 理解成不使用nums[i],dp[j-nums[i]]为使用nums[i],因为倒序遍历背包容量,是利用了i-1的基础上。
            }
        }

        return dp[size];  
    }
}

二维的形式:

相当于二维形式的 递推公式:dp[i] [j] =dp[i-1] [j]+dp[i-1] [j-nums[i ]] , 一个使用 一个不使用

474、一零和

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集

示例 1:

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

本题中strs 数组里的元素就是物品,每个物品都有两个维度!

而m 和 n相当于是一个背包,两个维度的背包

所以还是背包问题!

注意使用的还是滚动数组,只不过是两个维度!

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {

        //dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
        int[][] dp=new int[m+1][n+1];
        for(String str:strs)   //遍历物品
        {
            int zeroNum =0;
            int oneNum=0;
            //计算每个物品的容量
            for(char ch:str.toCharArray())
            {
                if(ch=='0')
                    zeroNum++;
                else if(ch=='1')
                    oneNum++;
            }
            //遍历背包
            for(int i=m;i>=zeroNum;i--)
            {
                for(int j=n;j>=oneNum;j--)
                {
                    //dp[i][j]是不选择物品str,dp[i-zeroNum][j-oneNum]+1是选择物品str
                    dp[i][j]=Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);  //倒序利用一维数组
                }
            }

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

此时我们讲解了0-1背包的多种应用,

  • 纯 0 - 1 背包 (opens new window)是求 给定背包容量 装满背包 的最大价值是多少。
  • 416. 分割等和子集 (opens new window)是求 给定背包容量,能不能装满这个背包。
  • 1049. 最后一块石头的重量 II (opens new window)是求 给定背包容量,尽可能装,最多能装多少
  • 494. 目标和 (opens new window)是求 给定背包容量,装满背包有多少种方法。
  • 本题是求 给定背包容量,装满背包最多有多少个物品。

完全背包理论基础

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件

我们知道01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的,所以要从小到大去遍历。

01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了,一维dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量

在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的!因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。即,正序遍历的时候两个for循环的数量是无所谓的!

全文我说的都是对于纯完全背包问题,其for循环的先后循环是可以颠倒的!

//先遍历物品,再遍历背包
private static void testCompletePack(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 0; i < weight.length; i++){ // 遍历物品
        for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

//先遍历背包,再遍历物品
private static void testCompletePackAnotherWay(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
        for (int j = 0; j < weight.length; j++){ // 遍历物品
            if (i - weight[j] >= 0){
                dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
            }
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

518、零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

纯完全背包是凑成背包最大价值是多少,而本题是要求凑成总金额的物品组合个数!

即组合问题,递推公式为dp[j] += dp[j - coins[i]];

纯完全背包的两个for循环的先后顺序都是可以的。但本题就不行了!

关于遍历顺序的问题:

我们先来看 外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况。

代码如下:

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}

假设:coins[0] = 1,coins[1] = 5。

那么就是先把1加入计算,然后再把5加入计算,得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数!

如果把两个for交换顺序,代码如下:

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数!

总结:

如果求组合数就是外层for循环遍历物品,内层for遍历背包

如果求排列数就是外层for遍历背包,内层for循环遍历物品

class Solution {
    public int change(int amount, int[] coins) {

        int[] dp=new int[amount+1];
        dp[0]=1;  //计数的时候初始化为0
        for(int i=0;i<coins.length;i++)
        {
            for(int j=coins[i];j<=amount;j++)
            {
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

377、组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。

示例 2:

输入:nums = [9], target = 3
输出:0

但其本质是本题求的是排列总和,而且仅仅是求排列总和的个数,并不是把所有的排列都列出来。

如果本题要把排列都列出来的话,只能使用回溯算法爆搜

动规五部曲分析如下:

1、确定dp数组以及下标的含义

dp[i]: 凑成目标正整数为i的排列个数为dp[i]

2、确定递推公式

dp[i](考虑nums[j])可以由 dp[i - nums[j]](不考虑nums[j]) 推导出来。

求装满背包有几种方法,递推公式一般都是dp[i] += dp[i - nums[j]];

3、dp数组如何初始化

因为递推公式dp[i] += dp[i - nums[j]]的缘故,dp[0]要初始化为1,这样递归其他dp[i]的时候才会有数值基础。

4、遍历顺序

如果求组合数就是外层for循环遍历物品,内层for遍历背包

如果求排列数就是外层for遍历背包,内层for循环遍历物品

所以本题遍历顺序最终遍历顺序:target(背包)放在外循环,将nums(物品)放在内循环,内循环从前到后遍历

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp =new int[target+1];
        dp[0]=1;
        for(int j=1;j<=target;j++)  //先遍历背包,在遍历物品
        {
            for(int i=0;i<nums.length;i++)
            {
                if(j>=nums[i])     //要保证容量大于等于物品
                    dp[j]+=dp[j-nums[i]];
            }

        }
        return dp[target];

    }
}

70、爬楼梯进阶版-ACM模式

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

输入描述:输入共一行,包含两个正整数,分别表示n, m

输出描述:输出一个整数,表示爬到楼顶的方法数。

输入示例:3 2

输出示例:3

提示:

当 m = 2,n = 3 时,n = 3 这表示一共有三个台阶,m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

  • 1 阶 + 1 阶 + 1 阶段
  • 1 阶 + 2 阶
  • 2 阶 + 1 阶

我们之前做的 爬楼梯 是只能至多爬两个台阶,采用的是最直接的动规方法(斐波那契)。

这次改为:一步一个台阶,两个台阶,三个台阶,…,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢?

这又有难度了,这其实是一个完全背包问题。

1阶,2阶,… m阶就是物品,楼顶就是背包。

每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题了!

这是背包里求排列问题,即:1、2 步 和 2、1 步都是上三个台阶,但是这两种方法不一样!

排列问题先遍历背包,再遍历物品。

每一步可以走多次,这是完全背包,内循环需要从前向后遍历。

import java.util.Scanner;
class climbStairs{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int m, n;
        while (sc.hasNextInt()) {
            // 从键盘输入参数,中间用空格隔开
            n = sc.nextInt();
            m = sc.nextInt();

            // 求排列问题,先遍历背包再遍历物品
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= m; i++) {
                    if (j - i >= 0) dp[j] += dp[j - i];
                }
            }
            System.out.println(dp[n]);
        }
    }
}

322、零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3 
解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3
输出:-1

示例 3:

输入:coins = [1], amount = 0
输出:0

动规五部曲分析如下:

1、确定dp数组以及下标的含义

dp[j]:凑足总额为j所需钱币的最少个数为dp[j]

2、确定递推公式

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3、dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;

其他下标对应的数值呢?

考虑到递推公式的特性,dp[j]必须初始化为一个最大的数,否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

4、确定遍历顺序

本题求钱币最小个数,你那么先遍历钱币和先遍历背包都是可以的,都不影响钱币的最小个数

5、举例推导dp数组

以输入:coins = [1, 2, 5], amount = 5为例

根据先遍历硬币,在遍历背包,模拟出过程:

coins[0]=1: 0 1 2 3 4 5

coins[1]=2: 0 1 1 2 2 3

coins[2]=5: 0 1 1 2 2 1

完全背包的求最小值问题:

不一定能凑成。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 1; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;  //dp[0]要初始化,因为后面会用到
        for (int i = 0; i < coins.length; i++) {
            //正序遍历:完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要
                if(dp[j - coins[i]] != max) 
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
    }
    return dp[amount] == max ? -1 : dp[amount];
}
}

279、 完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:

输入:n = 12
输出:3 
解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9

我来把题目翻译一下:完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品?

递推公式:所以递推公式:dp[j] = min(dp[j - i * i] + 1, dp[j]);

完全背包的求最小值问题:

本题一定能凑成。

class Solution {
    public int numSquares(int n) {
        int max=Integer.MAX_VALUE;
        int[] dp=new int[n+1];  //n相当于背包的重量

        for(int i=1;i<dp.length;i++)
        {
            dp[i]=max;
        }
        dp[0]=0;
        for(int i=1;i<=Math.sqrt(n);i++)  //i相当于物品
        {
            for(int j=i*i;j<=n;j++)    //j要从i*i开始,是背包容量
            {
                if(dp[j-i*i]!=max)   //dp[j-i*i] 不是初始值的时候
                    dp[j]=Math.min(dp[j],dp[j-i*i]+1);
            }

        }
        return dp[n];
    }
}

139、单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意,你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

1、确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词

2、确定递推公式

如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

3、dp数组如何初始化

从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。

4、遍历顺序

不同的顺序组成的单词不同,所以是排列问题。

字符串s相当于背包,字符串列表相当于每个物品。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {

        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        //因为是有序的,先遍历背包,在遍历物品
        for(int i=1;i<=s.length();i++)
        {
            for(String word:wordDict)
            {
                int len=word.length();
                //因为先遍历背包的,因此容量要大于len
                if(i>=len &&dp[i-len] && word.equals(s.substring(i-len,i)))
                {
                    dp[i]=true;
                }
            }
        }
        return dp[s.length()];
    }
}

背包问题总结

在讲解背包问题的时候,我们都是按照如下五部来逐步分析,相信大家也体会到,把这五部都搞透了,算是对动规来理解深入了。

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

其实这五部里哪一步都很关键,但确定递推公式和确定遍历顺序都具有规律性和代表性,所以下面我从这两点来对背包问题做一做总结

递推公式:

问能否能装满背包(或者最多装多少):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ,对应题目如下:

  • 动态规划:416.分割等和子集(opens new window)
  • 动态规划:1049.最后一块石头的重量 II(opens new window)

问装满背包有几种方法:dp[j] += dp[j - nums[i]] ,对应题目如下:

  • 动态规划:494.目标和(opens new window)
  • 动态规划:518. 零钱兑换 II(opens new window)
  • 动态规划:377.组合总和Ⅳ(opens new window)
  • 动态规划:70. 爬楼梯进阶版(完全背包)(opens new window)

问背包装满最大价值:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ,对应题目如下:

  • 动态规划:474.一和零(opens new window)

问装满背包所有物品的最小个数:dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ,对应题目如下:

  • 动态规划:322.零钱兑换(opens new window)
  • 动态规划:279.完全平方数(opens new window)

遍历顺序:

01背包

在动态规划:关于01背包问题,你该了解这些! (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。

和动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中,我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历。

一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的,大家需要注意!

完全背包

说完01背包,再看看完全背包。

在动态规划:关于完全背包,你该了解这些! (opens new window)中,讲解了纯完全背包的一维dp数组实现,先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的,题目稍有变化,两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品,内层for遍历背包

如果求排列数就是外层for遍历背包,内层for循环遍历物品

相关题目如下:

  • 求组合数:动态规划:518.零钱兑换II(opens new window)
  • 求排列数:动态规划:377. 组合总和 Ⅳ (opens new window)、动态规划:70. 爬楼梯进阶版(完全背包)(opens new window)

如果求最小数,那么两层for循环的先后顺序就无所谓了,相关题目如下:

  • 求最小数:动态规划:322. 零钱兑换 (opens new window)、动态规划:279.完全平方数(opens new window)

对于背包问题,其实递推公式算是容易的,难是难在遍历顺序上,如果把遍历顺序搞透,才算是真正理解了

即:

一维dp数组01背包只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历。完全背包与01背包的区别就是,完全背包的背包容量要从小到大正序遍历。

如果求组合数就是外层for循环遍历物品,内层for遍历背包

如果求排列数就是外层for遍历背包,内层for循环遍历物品

做题的时候要从四个方面考虑,dp的定义,递归函数、初始化,遍历顺序

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/899703.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

实战 | 国外攻破大学数据库系统,暴露数千学生记录

实战 | 国外攻破大学数据库系统&#xff0c;暴露数千学生记录 引言 在这篇文章中&#xff0c;我将分享我是如何攻破一个大型大学解决方案门户服务器的&#xff0c;这个服务器服务于许多大学客户&#xff0c;并且涉及数千名学生的数据。 目标 这是一个由印度许多大学和学院使…

没有基础,学习HCIE难吗?

首先要清楚&#xff0c;华为 HCIE-Datacom 认证并非局限于特定专业背景&#xff0c;即便对专业基础有一定要求&#xff0c;无论你有无相关学习经历或者工作经验&#xff0c;皆有机会报考并争取通过这一认证。HCIE-Datacom 考试主要由笔试和实验两部分构成&#xff0c;涉及高级路…

elf加载,动态库加载

elf加载 ELF&#xff08;Executable and Linkable Format&#xff0c;可执行与可链接格。 所以我们写代码生成的可执行文件&#xff0c;以及写的动态库都是elf格式的文件。 我们重点要关注的就是红色框框里面的section节。 而节保存的就有我们的代码段和数据段。所以我们链接…

Redis 性能优化选择:Pika 的配置与使用详解

引言 在我们日常开发中 redis是我们开发业务场景中不可缺少的部分。Redis 凭借其内存存储和快速响应的特点&#xff0c;广泛应用于缓存、消息队列等各种业务场景。然而&#xff0c;随着数据量的不断增长&#xff0c;单节点的 Redis 因为内存限制和并发能力的局限&#xff0c;逐…

ONLYOFFICE文档8.2:开启无缝PDF协作

ONLYOFFICE 开源办公套件的最新版本新增约30个新功能&#xff0c;并修复了超过500处故障。 什么是 ONLYOFFICE 文档 ONLYOFFICE 文档是一套功能强大的文档编辑器&#xff0c;支持编辑处理文档、表格、幻灯片、可填写的表单和PDF。可多人在线协作&#xff0c;支持插件和 AI 集…

论文解读 | ECCV2024 AutoEval-Video:一个用于评估大型视觉-语言模型在开放式视频问答中的自动基准测试...

点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入&#xff01; 点击 阅读原文 观看作者讲解回放&#xff01; 作者简介 陈修元&#xff0c;上海交通大学清源研究院硕士生 概述 总结来说&#xff0c;我们提出了一个新颖且具有挑战性的基准测试AutoEvalVideo&#xff0c;用于全…

红队-安全见闻篇(上)

声明 学习视频来自B站UP主 泷羽sec的个人空间-泷羽sec个人主页-哔哩哔哩视频,如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 一.编程与开发 1.后端语言学习 C语⾔&#xff1a;⼀种通⽤的…

NVR小程序接入平台/设备EasyNVR多个NVR同时管理的高效解决方案

在当今的数字化安防时代&#xff0c;视频监控系统的需求日益复杂和多样化。为了满足不同场景下的监控需求&#xff0c;一种高效、灵活且兼容性强的安防视频监控平台——NVR批量管理软件/平台EasyNVR应运而生。本篇探讨这一融合所带来的创新与发展。 一、NVR监测软件/设备EasyNV…

053_python基于深度学习的短视频内容理解与推荐系统

目录 系统展示 开发背景 代码实现 项目案例 获取源码 博主介绍&#xff1a;CodeMentor毕业设计领航者、全网关注者30W群落&#xff0c;InfoQ特邀专栏作家、技术博客领航者、InfoQ新星培育计划导师、Web开发领域杰出贡献者&#xff0c;博客领航之星、开发者头条/腾讯云/AW…

如何实现海内外工厂的EDI对接?

企业在国际市场的扩张需要高效的信息流动&#xff0c;以便快速响应客户需求。但国内工厂和海外工厂使用的系统可能存在兼容性问题&#xff0c;且数据格式各不相同&#xff0c;集成过程复杂。 近期国内主营高精度滚动轴承的汽车行业C公司就遇到了这样的挑战&#xff0c;如何实现…

linux查看文件命令

查看文件命令 显示命令 cat 语法&#xff1a;cat 【选项】 文件 选项 命令含义n显示行号包括空行b显示行号不包括空行s压缩空行为一行A显示隐藏字符 cat -n 文件&#xff1a;显示行号包括空行 cat -b 文件 cat -s 文件 cat -A 文件 more和less是 分页查看 tac和rev都…

python实战项目47:Selenium采集百度股市通数据

python实战项目47:Selenium采集百度股市通数据 一、思路分析二、完整代码一、思路分析 这里以获取百度股市通股评下的投票数据为例,页面中的其他数据同理。由于此页面数据是js动态加载的,所以采用Selenium获取数据。思路很简单,通过Selenium打开页面,然后定位到“股评”选…

502 错误码通常出现在什么场景?

服务器过载场景 高流量访问&#xff1a;当网站遇到突发的高流量情况&#xff0c;如热门产品促销活动、新闻热点事件导致网站访问量激增时&#xff0c;服务器可能会因承受过多请求而无法及时响应。例如&#xff0c;电商平台在 “双十一” 等购物节期间&#xff0c;大量用户同时…

Java 多线程(七)—— 定时器

定时器介绍与使用 先简单介绍一下什么是定时器&#xff1a;定时器类似生活中的闹钟&#xff0c;当时间一到&#xff0c;我们就会去做某些事情。 在代码层面理解就是&#xff0c;当我们设置的时间一到&#xff0c;程序就会执行我们固定的代码片段&#xff08;也就是任务&#x…

Nacos-Sync-未授权进后台(建议自查)

Nacos-Sync-未授权进后台&#xff08;建议自查&#xff09; 漏洞成因 没进行权限校验。 影响范围 Nacos-Sync 3.0 发现方式 一、fofa发现 title“nacos” && title“Nacos-Sync” 二、路径拼接 /#/serviceSync 利用方式 访问之后直接是进入后台的样子~ 修复方…

【AI视频抠图整合包及教程】开启视觉分割新纪元 —— Meta SAM 2

在数字化时代&#xff0c;Meta公司推出的SAM 2&#xff08;Segment Anything Model 2&#xff09;标志着图像和视频分割技术的一个新高度。SAM 2不仅继承了前代SAM模型的卓越性能&#xff0c;更在实时处理、视频分割、交互式提示等方面实现了重大突破。以下是SAM 2的全面营销文…

【植物识别系统】Python+人工智能+深度学习+卷积神经网络算法+TensorFlow+算法模型+Django网页界面平台

一、介绍 植物识别系统&#xff0c;使用Python作为主要编程语言开发&#xff0c;通过收集常见的6中植物树叶&#xff08;‘广玉兰’, ‘杜鹃’, ‘梧桐’, ‘樟叶’, ‘芭蕉’, ‘银杏’&#xff09;图片作为数据集&#xff0c;然后使用TensorFlow搭建ResNet50算法网络模型&am…

如何通过Lua语言请求接口拿到数据

文章目录 概要http客户端通过请求下载数据 概要 当某个需求是需要在模块内请求接口拿到数据&#xff0c;需要使用http客户端调用接口 http客户端 LuaSOC请求接口官方文档 调用&#xff1a;http.request(method,url,headers,body,opts,ca_file,client_ca, client_key, clien…

【日记】感觉沟通是件很难精通的事情(1397 字)

正文 今天霜降&#xff0c;感觉得开始戴手套了&#xff0c;去年就是因为戴得早&#xff0c;所以避免了生冻疮。不知道今年还会不会有这么幸运。虽然霜降&#xff0c;但意外地天气很好呢。下午又找了个时间稍微偷溜出去发了一会儿呆。可惜每次下班天都黑了&#xff0c;天气好的话…

HCIP--1

同一区域内的OSPF路由器拥有一致的 LSDB, 在区域内&#xff0c;OSPF 采用 SPF算法计算路由一个区域太多路由器&#xff0c;硬件资源跟不上&#xff0c;所以多划分区域 OSPF 路由计算原理 1. 区域内路由计算 LSA 在OSPF中&#xff0c;每个路由器生成 LSA&#xff0c;用于告诉…