class083 动态规划中用观察优化枚举的技巧-下【算法】

这篇具有很好参考价值的文章主要介绍了class083 动态规划中用观察优化枚举的技巧-下【算法】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

class083 动态规划中用观察优化枚举的技巧-下【算法】

算法讲解083【必备】动态规划中用观察优化枚举的技巧-下

class083 动态规划中用观察优化枚举的技巧-下【算法】,左程云算法,算法,动态规划

code1 1235. 规划兼职工作

// 规划兼职工作
// 你打算利用空闲时间来做兼职工作赚些零花钱,这里有n份兼职工作
// 每份工作预计从startTime[i]开始、endTime[i]结束,报酬为profit[i]
// 返回可以获得的最大报酬
// 注意,时间上出现重叠的 2 份工作不能同时进行
// 如果你选择的工作在时间X结束,那么你可以立刻进行在时间X开始的下一份工作
// 测试链接 : https://leetcode.cn/problems/maximum-profit-in-job-scheduling/

利用观察单调性 + 二分搜索的方式优化枚举,最优解时间复杂度O(n*logn)

dp[i]:[0…i]的最大报酬
不需要i位置的工作:dp[i-1]
需要i位置的工作:profit[i]+dp[j]:j是结束时间不超过startTime[i]的最右的

package class083;

import java.util.Arrays;

// 规划兼职工作
// 你打算利用空闲时间来做兼职工作赚些零花钱,这里有n份兼职工作
// 每份工作预计从startTime[i]开始、endTime[i]结束,报酬为profit[i]
// 返回可以获得的最大报酬
// 注意,时间上出现重叠的 2 份工作不能同时进行
// 如果你选择的工作在时间X结束,那么你可以立刻进行在时间X开始的下一份工作
// 测试链接 : https://leetcode.cn/problems/maximum-profit-in-job-scheduling/
public class Code01_MaximumProfitInJobScheduling {

	public static int MAXN = 50001;

	public static int[][] jobs = new int[MAXN][3];

	public static int[] dp = new int[MAXN];

	public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
		int n = startTime.length;
		for (int i = 0; i < n; i++) {
			jobs[i][0] = startTime[i];
			jobs[i][1] = endTime[i];
			jobs[i][2] = profit[i];
		}
		// 工作按照结束时间从小到大排序
		Arrays.sort(jobs, 0, n, (a, b) -> a[1] - b[1]);
		dp[0] = jobs[0][2];
		for (int i = 1, start; i < n; i++) {
			start = jobs[i][0];
			dp[i] = jobs[i][2];
			if (jobs[0][1] <= start) {
				dp[i] += dp[find(i - 1, start)];
			}
			dp[i] = Math.max(dp[i], dp[i - 1]);
		}
		return dp[n - 1];
	}

	// job[0...i]范围上,找到结束时间 <= start,最右的下标
	public static int find(int i, int start) {
		int ans = 0;
		int l = 0;
		int r = i;
		int m;
		while (l <= r) {
			m = (l + r) / 2;
			if (jobs[m][1] <= start) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans;
	}

}

code2 629. K 个逆序对数组

// K个逆序对数组
// 逆序对的定义如下:
// 对于数组nums的第i个和第j个元素
// 如果满足0<=i<j<nums.length 且 nums[i]>nums[j],则为一个逆序对
// 给你两个整数n和k,找出所有包含从1到n的数字
// 且恰好拥有k个逆序对的不同的数组的个数
// 由于答案可能很大,只需要返回对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/

最优解 利用观察 + 构造窗口累加和,已经进入 观察并设计高效的查询结构 的范畴了
只不过这个结构就仅存在于概念,并用一个int类型的变量维护而已

package class083;

// K个逆序对数组
// 逆序对的定义如下:
// 对于数组nums的第i个和第j个元素
// 如果满足0<=i<j<nums.length 且 nums[i]>nums[j],则为一个逆序对
// 给你两个整数n和k,找出所有包含从1到n的数字
// 且恰好拥有k个逆序对的不同的数组的个数
// 由于答案可能很大,只需要返回对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/
public class Code02_KInversePairsArray {

	// 最普通的动态规划
	// 不优化枚举
	public static int kInversePairs1(int n, int k) {
		int mod = 1000000007;
		// dp[i][j] : 1、2、3...i这些数字,形成的排列一定要有j个逆序对,请问这样的排列有几种
		int[][] dp = new int[n + 1][k + 1];
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			dp[i][0] = 1;
			for (int j = 1; j <= k; j++) {
				if (i > j) {
					for (int p = 0; p <= j; p++) {
						dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
					}
				} else {
					// i <= j
					for (int p = j - i + 1; p <= j; p++) {
						dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
					}
				}
			}
		}
		return dp[n][k];
	}

	// 根据观察方法1优化枚举
	// 最优解
	// 其实可以进一步空间压缩
	// 有兴趣的同学自己试试吧
	public static int kInversePairs2(int n, int k) {
		int mod = 1000000007;
		int[][] dp = new int[n + 1][k + 1];
		dp[0][0] = 1;
		// window : 窗口的累加和
		for (int i = 1, window; i <= n; i++) {
			dp[i][0] = 1;
			window = 1;
			for (int j = 1; j <= k; j++) {
				if (i > j) {
					window = (window + dp[i - 1][j]) % mod;
				} else {
					// i <= j
					window = ((window + dp[i - 1][j]) % mod - dp[i - 1][j - i] + mod) % mod;
				}
				dp[i][j] = window;
			}
		}
		return dp[n][k];
	}

}

code3 514. 自由之路

// 自由之路
// 题目描述比较多,打开链接查看
// 测试链接 : https://leetcode.cn/problems/freedom-trail/

优化枚举的核心是贪心策略:
下一步做枚举时,不需要枚举所有可能性,只需要枚举 顺时针的最近、逆时针的最近 两种可能性即可

贪心当然会有专题讲述!【必备】课程的动态规划专题结束了,就会开始贪心的专题

package class083;

// 自由之路
// 题目描述比较多,打开链接查看
// 测试链接 : https://leetcode.cn/problems/freedom-trail/
public class Code03_FreedomTrail {

	// 为了让所有语言的同学都可以理解
	// 不会使用任何java语言自带的数据结构
	// 只使用最简单的数组结构
	public static int MAXN = 101;

	public static int MAXC = 26;

	public static int[] ring = new int[MAXN];

	public static int[] key = new int[MAXN];

	public static int[] size = new int[MAXC];

	public static int[][] where = new int[MAXC][MAXN];

	public static int[][] dp = new int[MAXN][MAXN];

	public static int n, m;

	public static void build(String r, String k) {
		for (int i = 0; i < MAXC; i++) {
			size[i] = 0;
		}
		n = r.length();
		m = k.length();
		for (int i = 0, v; i < n; i++) {
			v = r.charAt(i) - 'a';
			where[v][size[v]++] = i;
			ring[i] = v;
		}
		for (int i = 0; i < m; i++) {
			key[i] = k.charAt(i) - 'a';
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				dp[i][j] = -1;
			}
		}
	}

	public static int findRotateSteps(String r, String k) {
		build(r, k);
		return f(0, 0);
	}

	// 指针当前指着轮盘i位置的字符,要搞定key[j....]所有字符,最小代价返回
	public static int f(int i, int j) {
		if (j == m) {
			// key长度是m
			// 都搞定
			return 0;
		}
		if (dp[i][j] != -1) {
			return dp[i][j];
		}
		int ans;
		if (ring[i] == key[j]) {
			// ring b
			//      i
			// key  b
			//      j
			ans = 1 + f(i, j + 1);
		} else {
			// 轮盘处在i位置,ring[i] != key[j]
			// jump1 : 顺时针找到最近的key[j]字符在轮盘的什么位置
			// distance1 : 从i顺时针走向jump1有多远
			int jump1 = clock(i, key[j]);
			int distance1 = (jump1 > i ? (jump1 - i) : (n - i + jump1));
			// jump2 : 逆时针找到最近的key[j]字符在轮盘的什么位置
			// distance2 : 从i逆时针走向jump2有多远
			int jump2 = counterClock(i, key[j]);
			int distance2 = (i > jump2 ? (i - jump2) : (i + n - jump2));
			ans = Math.min(distance1 + f(jump1, j), distance2 + f(jump2, j));
		}
		dp[i][j] = ans;
		return ans;
	}

	// 从i开始,顺时针找到最近的v在轮盘的什么位置
	public static int clock(int i, int v) {
		int l = 0;
		// size[v] : 属于v这个字符的下标有几个
		int r = size[v] - 1, m;
		// sorted[0...size[v]-1]收集了所有的下标,并且有序
		int[] sorted = where[v];
		int find = -1;
		// 有序数组中,找>i尽量靠左的下标
		while (l <= r) {
			m = (l + r) / 2;
			if (sorted[m] > i) {
				find = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		// 找到了就返回
		// 没找到,那i顺指针一定先走到最小的下标
		return find != -1 ? sorted[find] : sorted[0];
	}

	public static int counterClock(int i, int v) {
		int l = 0;
		int r = size[v] - 1, m;
		int[] sorted = where[v];
		int find = -1;
		// 有序数组中,找<i尽量靠右的下标
		while (l <= r) {
			m = (l + r) / 2;
			if (sorted[m] < i) {
				find = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		// 找到了就返回
		// 没找到,那i逆指针一定先走到最大的下标
		return find != -1 ? sorted[find] : sorted[size[v] - 1];
	}

}

code4 未排序数组中累加和小于或等于给定值的最长子数组长度

// 累加和不大于k的最长子数组
// 给定一个无序数组arr,长度为n,其中元素可能是正、负、0
// 给定一个整数k,求arr所有的子数组中累加和不大于k的最长子数组长度
// 要求时间复杂度为O(n)
// 测试链接 : https://www.nowcoder.com/practice/3473e545d6924077a4f7cbc850408ade
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

强烈推荐先看一下讲解046

利用构造单调数组 + 二分搜索的解不是最优解,时间复杂度O(n*logn)

最优解中包含的贪心思想(窗口的加速建立、可能性的淘汰),是这个题的重点,时间复杂度O(n)

贪心当然会有专题讲述!【必备】课程的动态规划专题结束了,就会开始贪心的专题

package class083;

// 累加和不大于k的最长子数组
// 给定一个无序数组arr,长度为n,其中元素可能是正、负、0
// 给定一个整数k,求arr所有的子数组中累加和不大于k的最长子数组长度
// 要求时间复杂度为O(n)
// 测试链接 : https://www.nowcoder.com/practice/3473e545d6924077a4f7cbc850408ade
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

// 至今的最优解,全网题解几乎都是我几年前讲的方法
public class Code04_LongestSubarraySumNoMoreK {

	public static int MAXN = 100001;

	public static int[] nums = new int[MAXN];

	public static int[] minSums = new int[MAXN];

	public static int[] minSumEnds = new int[MAXN];

	public static int n, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			k = (int) in.nval;
			for (int i = 0; i < n; i++) {
				in.nextToken();
				nums[i] = (int) in.nval;
			}
			out.println(compute2());
		}
		out.flush();
		out.close();
		br.close();
	}

	public static int compute1() {
		int[] sums = new int[n + 1];
		for (int i = 0, sum = 0; i < n; i++) {
			// sum : 0...i范围上,这前i+1个数字的累加和
			sum += nums[i];
			// sums[i + 1] : 前i+1个,包括一个数字也没有的时候,所有前缀和中的最大值
			sums[i + 1] = Math.max(sum, sums[i]);
		}
		int ans = 0;
		for (int i = 0, sum = 0, pre, len; i < n; i++) {
			sum += nums[i];
			pre = find(sums, sum - k);
			len = pre == -1 ? 0 : i - pre + 1;
			ans = Math.max(ans, len);
		}
		return ans;
	}

	public static int find(int[] sums, int num) {
		int l = 0;
		int r = n;
		int m = 0;
		int ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (sums[m] >= num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	public static int compute2() {
		minSums[n - 1] = nums[n - 1];
		minSumEnds[n - 1] = n - 1;
		for (int i = n - 2; i >= 0; i--) {
			if (minSums[i + 1] < 0) {
				minSums[i] = nums[i] + minSums[i + 1];
				minSumEnds[i] = minSumEnds[i + 1];
			} else {
				minSums[i] = nums[i];
				minSumEnds[i] = i;
			}
		}
		int ans = 0;
		for (int i = 0, sum = 0, end = 0; i < n; i++) {
			while (end < n && sum + minSums[end] <= k) {
				sum += minSums[end];
				end = minSumEnds[end] + 1;
			}
			if (end > i) {
				// 如果end > i,
				// 窗口范围:i...end-1,那么窗口有效
				ans = Math.max(ans, end - i);
				sum -= nums[i];
			} else {
				// 如果end == i,那么说明窗口根本没扩出来,代表窗口无效
				// end来到i+1位置,然后i++了
				// 继续以新的i位置做开头去扩窗口
				end = i + 1;
			}
		}
		return ans;
	}

}

2023-12-10 12:31:44文章来源地址https://www.toymoban.com/news/detail-801652.html

到了这里,关于class083 动态规划中用观察优化枚举的技巧-下【算法】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法思想—枚举、递推、迭代、递归、分治、贪心、动态规划、回溯、模拟、分支定界

    算法思想 枚举(暴力算法) 枚举算法(暴力算法)是一种通过逐一尝试所有可能解来解决问题的算法。它的基本思想是将问题的所有可能答案一一列举出来,并根据一定的判断条件来确定哪些答案是合适的。这种算法通常使用循环来实现,因为需要尝试所有可能的情况。两

    2024年02月01日
    浏览(39)
  • 动态规划法及其优化

    在很多问题中,动态规划算法是我们的最优选择,比起递归算法,动态规划算法的时间复杂度和空间复杂度都更加优越,可以处理的数据规模更大。但是,动态优化算法的时间复杂度为O(N*V),也就是说,当需要处理的数据规模较大时,使用动态规划算法也存在超时的可能性

    2024年02月05日
    浏览(45)
  • [动态规划] 01背包问题及其优化

    题目描述 给一个能承重V的背包,和n件物品,我们用重量和价值的二元组来表示一个物品,第i件物品表示为(Vi,Wi),问:在背包不超重的情况下,得到物品的最大价值是多少? 输入 第一行输入两个数 V,n,分别代表背包的最大承重和物品数。 接下来n行,每行两个数Vi,W

    2024年02月03日
    浏览(45)
  • 基于动态规划的水库优化调度

       动态规划是最优化领域中的一个重要分支,是一种研究 多段决策 过程的递推最优化方法。所谓多段决策过程,是指根据时间、空间或其它特性可将过程分为若干互相联系的阶段,而在每个阶段必须作出决策的过程。凡是能作为多段决策过程来考虑的问题,都可应用动态

    2024年02月14日
    浏览(40)
  • 动态规划——矩阵优化DP 学习笔记

    前置知识:矩阵、矩阵乘法。 斐波那契数列 在斐波那契数列当中, (f_1 = f_2 = 1) , (f_i = f_{i - 1} + f_{i - 2}) ,求 (f_n) 。 而分析式子可以知道,求 (f_k) 仅与 (f_{k - 1}) 和 (f_{k - 2}) 有关; 所以我们设矩阵 (F_i = begin{bmatrix} f_{i - 1} f_{i - 2} end{bmatrix}) 。 设矩阵 (text{Ba

    2024年02月08日
    浏览(56)
  • 周赛347(模拟、思维题、动态规划+优化)

    难度简单1 给你一个用字符串表示的正整数 num ,请你以字符串形式返回不含尾随零的整数 num 。 示例 1: 示例 2: 提示: 1 = num.length = 1000 num 仅由数字 0 到 9 组成 num 不含前导零 模拟 难度中等4 给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ,请你求解大小同样为 m x

    2024年02月06日
    浏览(44)
  • 动态规划——斜率优化DP 学习笔记

    适用于求解最优解(最大、最小)问题。 可以将转移方程可以化为 (left[begin{array}{rl} 仅与 space i space 有关 是我们想要最大/最小化的 \\\\ 仅与 space j space 有关 是已知的 \\\\ 与 space i space 和 space j space 都有关 是两项相乘 end{array}right]) 三部分的, 都可以考虑用斜率优化

    2024年02月08日
    浏览(47)
  • 强化学习基础三大优化方法:(一)动态规划

    强化学习是一类解决马尔可夫决策过程的方法,其中, 动态规划、蒙特卡洛 以及 时序差分 是强化学习算法的三大基础算法。本文就其实际效果来对比三种方法以及其子方法的不同与优缺点。本文就动态规划方法进行简单介绍。 动态规划是一类优化方法,在给定一个马尔可

    2024年02月08日
    浏览(82)
  • 01背包问题----动态规划 -----python代码、优化

    问题描述: 容量为C的背包选择装物品,有n个物品,它们有各自的体积wi和价值vi,如何让背包里装入的物品具有最大价值? 解题思路: 也就是n个物品选择装入背包,每个物品都有两种选择,是(1)或否(0), 建模:       xi表示当前第i个物品是否选择,xi取值为(0,1)

    2024年02月04日
    浏览(55)
  • 15.动态规划:数据结构优化DP

    数据结构优化DP有前缀和、滑动窗口、树状数组、线段树、单调栈、单调队列 中等 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2

    2024年02月03日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包