13.动态规划
一.连续子数组的最大和
1.题目描述：
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
2.示例：
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6
3.解:
（1）我的答案：
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (dp[i - 1] >= 0) dp[i] = dp[i - 1] + nums[i];
else dp[i] = nums[i];
max = Math.max(dp[i], max);
}
return max;
}
}（1）网友答案：
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0, max = nums[0];
for (int num : nums) {
sum += num;
max = Math.max(max, sum);
if (sum < 0) sum = 0;
}
return max;
}
}class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}4.总结
网友答案的第一个解是最简单的解法，第二种是动态规划，它的动态规划空间复杂度比我的答案写的小，它是在原num数组的基础上更新子问题的解的。我的另外创建了一个缓存数组，存储每一个子问题的解。
动态规划：1.从问题中看出子问题解的定义是什么 2.建立缓存，记录每个子问题的解 3.回溯（从最小问题的解回溯，得到整个问题的解）
二.斐波那契数列
1.题目描述：
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
2.示例：
输入：n = 2
输出：1
3.解:
（1）我的答案：
class Solution {
public int fib(int n) {
if(n<2) return n;
else return (fib(n-1)+fib(n-2))%1000000007;
}
}class Solution {
public int fib(int n) {
if (n < 2) return n;
int dp1 = 0, dp2 = 1;
int temp = 0;
for (int i = 1; i < n; i++) {
temp = dp2;
dp2 = (dp1 + dp2) % 1000000007;
dp1 = temp;
}
return dp2;
}
}（2）网友答案：
class Solution {
public int fib(int n) {
if (n < 2) return n;
int dp1 = 0, dp2 = 1;
for (int i = 1; i < n; i++) {
int q = dp2;
dp2 = (dp2 + dp1) % (int)(1e9 + 7);
dp1 = q;
}
return dp2;
}
}4.总结
本质上是考察递归，但是这道题目用递归，有的用例会超出时间限制。总之，知道如何递归就行了。如果不想使它超出时间限制，那么就使用我的第二个答案/网友的答案，即动态规划。
三.按摩师
1.题目描述：
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
2.示例：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
3.解:
（1）我的答案:
class Solution {
public int massage(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
if (nums.length == 2) return Math.max(nums[0], nums[1]);
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
return dp[dp.length - 1];
}
}四.第 k 个数
1.题目描述：
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
2.示例：
输入: k = 5
输出: 9
3.解:
（1）我的答案：
class Solution {
public int getKthMagicNumber(int k) {
int[] uglyNums = new int[k]; // 丑数集合
// 3 , 5 , 7 的指针
int index3 = 0;
int index5 = 0;
int index7 = 0;
uglyNums[0] = 1;
for (int i = 1; i < k; i++) {
uglyNums[i] = Math.min(uglyNums[index3] * 3, Math.min(uglyNums[index5] * 5, uglyNums[index7] * 7));
if (uglyNums[i] == uglyNums[index3] * 3) index3++;
if (uglyNums[i] == uglyNums[index5] * 5) index5++;
if (uglyNums[i] == uglyNums[index7] * 7) index7++;
}
return uglyNums[k-1];
}
}4.总结
（1）动态规划的第一个问题，当前问题从哪里来。答案是从三个子问题来，即3，5，7的指针和所指向的元素值。
（2）动态规划的第二个问题，知道了从哪里来，我要做什么。答案是3，5，7指针指向的元素分别乘以3，5，7，选取最小值作为当前元素，并改变对应指针的值指向当前元素。
五.最大黑方阵
1.题目描述：
给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
2.示例：
输入:
[
[1,0,1],
[0,0,1],
[0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
输入:
[
[0,1,1],
[1,0,1],
[1,1,0]
]
输出: [0,0,1]
3.解:
class Solution {
private int[] res;
public int[] findSquare(int[][] matrix) {
int rowLen = matrix.length;
int colLen = matrix[0].length;
int[][] downMax = new int[rowLen][colLen];//记录矩阵中每个节点向下连续为0的长度
int[][] rightMax = new int[rowLen][colLen];//记录矩阵中每个节点向右连续为0的长度
int[] res = new int[3];//结果集
//遍历，填充downMax和rightMax
for (int i = rowLen - 1; i >= 0; i--) {
for (int j = colLen - 1; j >= 0; j--) {
if (matrix[i][j] == 0) {
downMax[i][j] = 1;
if (i < rowLen - 1) downMax[i][j] += downMax[i + 1][j];
rightMax[i][j] = 1;
if (j < colLen - 1) rightMax[i][j] += rightMax[i][j + 1];
}
}
}
//遍历matrix中的每个元素，判断以当前遍历元素为左上角的每个正方形矩阵是否四条边全为0，且尺寸大于res当前所记录的，就更新结果集
for (int i = 0; i < rowLen; i++) {
for (int j = 0; j < colLen; j++) {
if (matrix[i][j] == 0) {
int curSize = res[2];//当前结果集中符合条件的正方形矩阵的边长
int size = Math.min(downMax[i][j], rightMax[i][j]);//取当前元素向下和向右连续为0的长度，取两个值的最小值作为候选的正方形矩阵的边长
// 取最小值而不是最大值的原因是，取最小值才能保证每个边上的元素都为0，而且取了最小值也只能保证两条边符合条件，接下来的操作就是判断另外两条边也符合条件
for (int tempSize = size; tempSize > curSize; tempSize--) {
//如果另外两条边的连续为0的长度大于等于tempSize,则以temp为边长的正方形矩阵四条边都满足条件，则更新结果集
if (downMax[i][j + tempSize - 1] >= tempSize && rightMax[i + tempSize - 1][j] >= tempSize) {
res[0] = i;
res[1] = j;
res[2] = tempSize;
break;
}
}
}
}
}
if (res[2] == 0) return new int[]{};
return res;
}
}4.总结
这题的题解我觉得不是动态规划，硬要说是动态规划，可能只有对矩阵中每个元素，判断以它为左上角的每个矩阵是否符合条件时，才勉强算是动态规划。
投递小红书等公司10个岗位