LeetCode——动态规划篇(二)

这篇具有很好参考价值的文章主要介绍了LeetCode——动态规划篇(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 刷题顺序及思路来源于代码随想录,网站地址:https://programmercarl.com 

目录

343. 整数拆分 - 力扣(LeetCode)

96. 不同的二叉搜索树 - 力扣(LeetCode)

416. 分割等和子集 - 力扣(LeetCode)

1049. 最后一块石头的重量 II - 力扣(LeetCode)


 

343. 整数拆分 - 力扣(LeetCode)

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

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

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
import java.util.Scanner;

/**
 * @author light
 * @Description 整数拆分
 * @create 2023-09-14 18:19
 */
public class IntegerBreakTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		System.out.println(integerBreak(n));
	}
	public static int integerBreak(int n) {
		 //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已,
                //并且,在本题中,我们分析 dp[0], dp[1]都是无意义的,
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ,再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
	}
}

96. 不同的二叉搜索树 - 力扣(LeetCode)

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

LeetCode——动态规划篇(二),做题总结,leetcode,动态规划,算法,java,01背包


/**
 * @author light
 * @Description 不同的二叉搜索树
 *
 * @create 2023-09-14 18:49
 */
public class NumTreesTest {
	public int numTrees(int n) {
		//1 确认dp数组及其含义:dp[i]:输入【i】,共有dp[i]种不同的二叉搜索树
		//也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ,都是一样的。
		//dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
		//j相当于是头结点的元素,从1遍历到i为止。
		int[] dp=new int[n+1];
		dp[0]=1;
		for (int i = 1; i <=n; i++) {
			for (int j = 1; j <=i; j++) {
				dp[i]+=dp[j-1]*dp[i-j];
			}
		}
		return dp[n];
	}
}

416. 分割等和子集 - 力扣(LeetCode)

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

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

/**
 * @author light
 * @Description 分割等和子集
 * @create 2023-09-15 9:23
 */
public class CanPartitionTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n= input.nextInt();
		int[] num=new int[n];
		for (int i = 0; i < n; i++) {
			num[i]=input.nextInt();
		}
		System.out.println(canPartition(num));
	}
	public static boolean canPartition(int[] nums) {
		// 不能均分,直接返回false
		int sum = 0;
		for (int n : nums) {
			sum += n;
		}
		if (sum % 2 != 0) {
			return false;
		}
		// 能均分,计算平均分
		int score = sum / 2;
		/**
		 * 回溯
		 * 	//标记数组
		 * 	boolean[] flag = new boolean[nums.length];
		 * Arrays.fill(flag, false);
		 * return helper(nums, flag, 0, score, 0);
		 *
		 */
		/**
		 * 动规:1.二维数组
		 * dp[i][j]:从[0-i]中任选,装进背包容量为j的背包,所获得的最大价值为dp[i][j]
		 *
		  int[][] dp=new int[nums.length][score+1];
		//初始化看背包容量:
		// 当背包容量为零时,背包中放不进任何一个物品--->初始化为零
		// 看物品:已经放入物品一个,若背包容量大于物品重量,背包中是物品的价值,否则--->0
		for (int i = 0; i < nums.length; i++) {
			dp[i][0]=0;
		}
		for (int i = 0; i <=score; i++) {
			if(i<nums[0]){
				dp[0][i]=0;
			}else{
				dp[0][i]=nums[0];
			}
		}
		for (int i = 1; i < nums.length; i++) {
			for (int j = 1; j <=score; j++) {
				if(j>=nums[i]){
					dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
				}else {
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		if(dp[nums.length-1][score]==score){
			return true;
		}else {
			return false;
		}

		 */

		/**
		 *  动规:2.滚动数组
		 *  dp[j]:背包容量为j的背包,所能容纳的最大价值为dp[j]
		 */
		int[] dp=new int[score+1];
		dp[0]=0;
		for (int i = 0; i < nums.length; i++) {
			for (int j = score; j>=nums[i] ; j--) {
				dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
			}
		}
		if(dp[score]==score){
			return true;
		}
		return false;


	}
	//回溯
	private  static  boolean helper(int[] nums,  boolean[] flag, int curnum, int score, int pos) {
		// 每一轮的终止条件:这一轮满足条件了,可以下一轮了
		if (curnum == score) {
			return true;
		}
		// 从头开始新的一轮,子集的累计和
		for (int i = pos; i < nums.length; i++) {
			if (flag[i]) {
				continue;
			}
			flag[i] = true;
			if(helper(nums, flag, curnum + nums[i], score, i + 1)){
				return true;
			}
			flag[i] = false;
		}
		return false;
	}
}

1049. 最后一块石头的重量 II - 力扣(LeetCode)

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

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

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

最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0文章来源地址https://www.toymoban.com/news/detail-732974.html

输入: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],这就是最优值。

import java.util.Scanner;

/**
 * @author light
 * @Description 最后一块石头的重量
 *
 *
 * (思路:尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。
 * @create 2023-09-21 15:03
 */
public class LastStoneWeightIITest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n= input.nextInt();
		int[] stones=new int[n];
		for (int i = 0; i < n; i++) {
			stones[i]=input.nextInt();
		}
		System.out.println(lastStoneWeightII(stones));
	}
	public static int lastStoneWeightII(int[] stones) {
		int sum=0;
		for (int n : stones) {
			sum += n;
		}
		int target = sum / 2;
		//dp[i][j]含义:任选[0-i] 个石头,装入容量为j的背包中,背包的最大重量为dp[i][j]
		int[][] dp=new int[stones.length][target+1];
		for (int i = 0; i < stones.length; i++) {
			dp[i][0]=0;
		}
		for (int i = 0; i <=target; i++) {
			if(i>=stones[0]){
				dp[0][i]=stones[0];
			}
		}
		for (int i = 1; i < stones.length; i++) {
			for (int j = 1; j <=target; j++) {
				if(j>=stones[i]){
					dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
				}else {
					dp[i][j]=dp[i-1][j];
				}

			}
		}
		return sum-dp[stones.length-1][target]-dp[stones.length-1][target];
	}
}

到了这里,关于LeetCode——动态规划篇(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】动态规划 ⑦ ( LeetCode 55. 跳跃游戏 | 算法分析 | 代码示例 )

    LeetCode 55. 跳跃游戏 : https://leetcode.cn/problems/jump-game/ 给定一个 非负整数数组 nums ,你最初位于数组的 第一个下标 0 位置 。 数组中的每个元素 代表你在该位置可以 跳跃的最大长度。 判断你 是否能够到达最后一个下标。 给定一个一维数组 , 数组元素不能有负数 , 如 : {2, 2,

    2024年02月10日
    浏览(38)
  • leetCode 2915. 和为目标值的最长子序列的长度 + 动态规划 +01背包 + 空间优化 + 记忆化搜索 + 递推

    2915. 和为目标值的最长子序列的长度 - 力扣(LeetCode) 给你一个下标从  0  开始的整数数组  nums  和一个整数  target  。返回和为  target  的  nums  子序列中,子序列  长度的最大值  。如果不存在和为  target  的子序列,返回  -1  。 子序列  指的是从原数组中删除一些

    2024年02月06日
    浏览(39)
  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(41)
  • LeetCode算法题解(动态规划)|LeetCoed62. 不同路径、LeetCode63. 不同路径 II

    题目链接:62. 不同路径 题目描述: 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 示例 2:

    2024年02月05日
    浏览(49)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(45)
  • 【算法|动态规划系列No.5】leetcode62. 不同路径

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(43)
  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月16日
    浏览(48)
  • leetcode877. 石子游戏(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/stone-game Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子,排成一行;每堆都有 正 整数颗石子,数目为 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ,所以没有平局。 Alice 和 Bob 轮流进行,Alic

    2024年02月10日
    浏览(56)
  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章: leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(52)
  • 【算法|动态规划No.15】leetcode1035. 不相交的线

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包