灌溉花园的最少水龙头数目【LC1326】
在 x 轴上有一个一维的花园。花园长度为n，从点 0 开始，到点 n 结束。
花园里总共有 n+1 个水龙头，分别位于 [0，1，...，n] 。
给你一个整数n和一个长度为n+1的整数数组ranges，其中ranges[i]（下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]] 。
请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。
过了的那一刻很是震惊 也许是昨天周赛刚看的01背包，也许不大恰当，但是我做出来了
01背包
- 思路：每个水龙头有选或者不选两种可能，因此转化为01背包问题
- 物品为每个水龙头的灌溉范围
- 背包容量为灌溉范围，表示背包能灌溉0−j范围内的花园。
- 定义状态dp[j]表示 灌溉范围为0−j时，所需要的最少水龙头数目。dp[n]即为最终结果
- 如果位置i的水龙头的灌溉范围为[l,r]=[i−ranges[i],i+ranges[i]]，枚举每一个灌溉范围小于r的背包，更新需要的水龙头数目。
- 一维动态规划
- 确定dp数组（dp table）以及下标的含义
dp[j]表示 灌溉范围为0−j时，所需要的最少水龙头数目。
- 确定递推公式
对于每一个位置的水龙头，更新其能灌溉的右范围
- 位置i不放水龙头：dp[j] =dp[j]
- 位置i放水龙头，该水龙头的灌溉范围记为[l,r]：
- dp数组如何初始化
当位置0的灌溉范围一定大于等于0，那么灌溉原点需要的最少水龙头数目为1
初始情况时其他的范围均灌溉不到，因此初始化为任意不可能的数值，我选择初始化为n+2，当最终结果dp[n]<n+2时，就表示可以灌溉整个花园
dp[0]= 1; dp[1,n] = n + 1;
- 确定遍历顺序
一维dp
先遍历物品，再从后往前遍历背包重量，将物品i放进能放进的背包j中 - 举例推导dp数组
class Solution { public int minTaps(int n, int[] ranges) { int[] dp = new int[n + 1]; Arrays.fill(dp, n + 2); dp[0] = 1; for (int i = 0; i <= n; i++){ int l = i - ranges[i], r = i + ranges[i]; for (int j = Math.min(r, n); j >= 0; j--){ if (l <= 0){ dp[j] = 1; }else{ dp[j] = Math.min(dp[l] + 1, dp[j]); } } } return dp[n] < n + 2 ? dp[n] : -1; } }
复杂度
- 时间复杂度：O(n2),n为数组长度
- 空间复杂度：O(n)，dp数组的额外空间
贪心
- 思路：
- 首先，对于所有能覆盖某个左端点的水龙头，选择能覆盖最远右端点的那个水龙头是最优的。【贪心】
- 那么，可以先预处理ranges数组，求出所有能覆盖左端点l的水龙头中，右端点最大的那个位置，记录在数组
rightMost[i]中。 - 那么从原点出发，记录当前所达到的右端点
cur和下一个可以达到的位置next
- 当
next与cur相等时，无法进行移动，返回-1 - 否则，移动到
next，步骤+1
class Solution { public int minTaps(int n, int[] ranges) { int[] rightMost = new int[n + 1]; for (int i = 0; i <= n; ++i) { int r = ranges[i]; // 这样写可以在 i>r 时少写一个 max // 凭借这个优化，恭喜你超越了 100% 的用户 // 说「超越」是因为原来的最快是 2ms，现在优化后是 1ms if (i > r) rightMost[i - r] = i + r; // 对于 i-r 来说，i+r 必然是它目前的最大值 else rightMost[0] = Math.max(rightMost[0], i + r); } int ans = 0; int curRight = 0; // 已建造的桥的右端点 int nextRight = 0; // 下一座桥的右端点的最大值 for (int i = 0; i < n; ++i) { // 注意这里没有遍历到 n，因为它已经是终点了 nextRight = Math.max(nextRight, rightMost[i]); if (i == curRight) { // 到达已建造的桥的右端点 if (i == nextRight) return -1; // 无论怎么造桥，都无法从 i 到 i+1 curRight = nextRight; // 造一座桥 ++ans; } } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/solutions/2123855/yi-zhang-tu-miao-dong-pythonjavacgo-by-e-wqry/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(n),n为数组长度
- 空间复杂度：O(n)，
rightMost数组的额外空间
