栅栏涂色
难度:
标签:
题目描述
代码结果
运行时间: 20 ms, 内存: 0.0 MB
/*
题目：栅栏涂色
题目思路：
假设我们有n个栅栏和k种颜色，我们需要找到一种方法来涂色，使得最多有两个连续的栅栏有相同的颜色。
使用Java Stream的思路：
1. 通过使用IntStream来模拟动态规划的递推关系。
2. 使用一个数组dp来存储same和diff的值。
*/
import java.util.stream.IntStream;
public class FencePaintingStream {
public int numWays(int n, int k) {
if (n == 0) return 0;
if (n == 1) return k;
int[] dp = new int[]{0, k};
IntStream.range(2, n + 1).forEach(i -> {
int same = dp[1];
int diff = (dp[0] + dp[1]) * (k - 1);
dp[0] = same;
dp[1] = diff;
});
return dp[0] + dp[1];
}
}
解释
方法:
这是一个动态规划问题。dp[i] 表示涂完前 i 根栅栏的方案数。对于第 i 根栅栏，我们有两种选择：
1. 如果它和前一根栅栏颜色相同，则它的方案数等于前一根栅栏与前前一根栅栏颜色不同的方案数，即 same = diff。
2. 如果它和前一根栅栏颜色不同，则它的方案数等于前一根栅栏的方案数乘以 (k-1)，即 diff = dp[i-1] * (k-1)。
最终，第 i 根栅栏的方案数等于 same + diff。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在解法中，为什么在初始化阶段`same, diff = 0, k`是合理的，特别是`same`初始化为0的原因是什么？
▷🦆
在动态规划的状态转移方程中，`same = diff`这一步的逻辑依据是什么？为什么能直接将diff的值赋给same？
▷🦆
对于`diff = dp[i-1] * (k-1)`这个表达式，能否详细解释为什么要乘以`(k-1)`并且这种计算方式是否考虑了所有可能的颜色组合？
▷🦆
算法对于特殊情况`n == 0 or n is None`进行了处理，返回0。为何选择在n为0时返回0，这里是否有其他合理的返回值？
▷相关问题
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3] 输出：3
提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000