526互联

[更新中][算法][动态规划][dynamic programing]力扣dp学习计划题单

发布时间 2023-03-26 12:07:08作者: Akira300000

最近开始跟着力扣的官方题单开始做题，先从动态规划开始做起，以后在此记录每周做的题目，做总结。

基本思路

动态规划利用递推或递归来解决问题，通常这个问题可以被拆分成相同的小问题，我们通过解决一个小问题继而解决更高一层的较大问题，整合其结果一直到原问题上。例如，斐波那契数列就是一个很典型的可以用动态规划解决的问题，因为其问题f(n)的值与其前两个值相关，因此这个问题就可以被拆分为f(i) = f(i-1) + f(i-2)并已知两个初值f(0), f(1)通过递推算出f(n)。
通常我们可以通过建表来记录f(i)的值，直到n>=i时。

int p=0, q=0, r=1;
for (int i=2; i <= n; ++i) {
   p = q; // assign q value to p
   q = r; // assign r value to q
   r = p + q; // f(n) = f(n-1)+f(n-2)
}
return r;

打劫问题(House Robber/Delete & Earn)

这类问题中的f(n)往往根据不同的情况有不同的算式，也就是说对任意值i，f(i)是或不是组成大问题的一部分，也就是在计算f(i)时判断是包含它还是跳过它。例如，打劫问题中小偷不能偷连续的房子，那么对于任意一栋房子，它可以是被偷(nums[i]+houses[i-2])或跳过(houses[i-1])：

houses[0] = nums[0];
houses[1] = max(nums[0], nums[1]);
for (int i=2; i<n; ++i) {
	houses[i] = max(nums[i]+houses[i-2], houses[i-1]);
}
return houses[n-1];

同理在delete & earn问题中，所有的某任意值i之前一个数m和之后一个数n会被删除，因此除了判断f(i)是保留还是跳过以外，还需要判断m和n与i的关系:

  • 求较大值
    • 保留：countElem[unique_elem[i]]+totalPts[i-2]
    • 跳过：totalPts[i-1]
  • 不是连续值
    • countElem[unique_elem[i]] + totalPts[i-1]全加起来了就完事了
      PS. totalPts[]存储各元素对应的最大点数; countElem[]存储原数组中重复元素的总和; unique_elem[]整合了原数组的元素，去掉重复部分。
for (int i=2; i<n; ++i) {
	totalPts[i] = (unique_elem[i]==unique_elem[i-1]+1)?
	(max(countElem[unique_elem[i]]+totalPts[i-2], totalPts[i-1])):
	(countElem[unique_elem[i]] + totalPts[i-1]);
}
return totalPts[n-1];

跳格子&最大子数组和(jump game/maximum subarray)

其实思路和打劫大差不差(只是我太菜了)，都是判断元素组的某一元素/格子/字符是包含还是跳过，判断依据都是根据题意找最大/最小值，而且不需要建表，而是使用指针表示现在的位置/值，并在每一次循环中依据题意更新指针，再更新最大/最小值。

Max Subarray 
// max subarray
int maxVal = nums[0], curMax = 0;
for (int& i:nums) {
	curMax = max(i, curMax+i);
	maxVal = max(maxVal, curMax); // update maxVal
}
return maxVal;
jump game 
// same idea as jump game
// to find the max jump length at [i, maxIndex] to decide the next position
int maxIndex = 0, minJumps = 0, currentStop = 0, nextStop = 0;
int n = nums.size();

if (n==1) return 0; // only one step, no jumps required
while (nextStop < n-1) { // jumping
	// find the maxIndex it can reach
	maxIndex = max(maxIndex, currentStop+nums[currentStop]);
	// if the current stop reach to the end of range
	if (currentStop == nextStop) {
		++minJumps; // increment jumps
		nextStop = maxIndex; // update the next stop
	}
	++currentStop; // update current stop
}
return minJumps;

环形数组求最大数组和(jump game II)

重点是确定范围，展开数组，根据情况重组，记住数组总和totalSum是固定值。

  • 若最大数组在原数组中间，则情况与跳跃游戏 I类似，只求maxVal；
  • 若最大数组在头尾交界处，则有一个最小数组在中间，即minVal = totalSum - maxVal.
    因此最大与最小，总和都需要计算。
    注意：当原数组只包含负数时，根据题意子数组不能为空，则maxVal = max(array), minVal = sum(array) = total。于是最后判断max(maxVal, total - minVal)时，返回0而不是maxVal，因此需要再加一层判断。
circular max subarray 
int maxVal = nums[0], minVal = nums[0], curMax = 0, curMin = 0, total = 0;

if (nums.size()==1) return nums[0];

for (int& i:nums) {
	curMax = max(i, curMax+i);    // update current maximum
	curMin = min(i, curMin+i);    // update current minimum
	maxVal = max(curMax, maxVal); // update maxVal
	minVal = min(curMin, minVal); // update minVal
	total += i;                   // update total sum
}
// in case that nums[] contains only negative numbers
return (minVal == total) ? maxVal : max(maxVal, total - minVal);