https://leetcode.com/problems/maximum-subarray/
Each question in DP seems to be different, but the ideas are consistent.
Today we start with a simple question.

Question:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

If you want to exhaust all subarrays, the time complexity reaches to O(n2). This is obviously Time Limit Exceeded, but I did…= =!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let max = nums[0]
for (let l = 0; l < nums.length; l++) {
for (let r = 0; r < nums.length; r++) {
let arr = nums.slice(l, r + 1)
if (arr.length) {
const s = sum(nums.slice(l, r + 1))
if (s > max) {
max = s
}
}
}
}
return max
}

// const sum = function(arr) {
// if (arr.length === 0) {
// return 0
// }
// if (arr.length === 1) {
// return arr[0]
// }
// return arr[0] + sum(arr.slice(1))
// }

const sum = arr => arr.reduce((acc, val) => acc + val)

Stupid boy…

DP is insteresting, let’s think about this problem.

Assume it begins from one item [1], when add a item to the array, you should consider if the previous item is a positive number.
If it’s a positive number, then we can calculate the sum of these two number, two good brother.
Otherwise, if the previous item is a negative number, these two are not good brother, we will not calculate the sum.

Attention, previous number can also be considered as previous sum, understand? Now we have completed the decomposition of the goal problem to sum problem:

maxSubArray(A, i) = A[i] + maxSubArray(A, i - 1) > 0 : maxSubArray(A, i - 1) : 0

i as the array size increases, maxSubArray(A, i - 1) means the previous sum.

1
2
3
4
5
6
7
8
9
var maxSubArray = function(A) {
let max = A[0]
let dp = []
dp[0] = A[0]
for (let i = 1; i < A.length; i++) {
dp[i] = A[i] + dp[i - 1] > 0 : dp[i - 1] : 0
max = Math.max(max, dp[i])
}
}

We can also reduse the complexity of space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let max = nums[0]
for (let i = 1; i < nums.length; i++) {
if (nums[i - 1] > 0) {
nums[i] += nums[i - 1]
}
max = Math.max(nums[i], max)
}
return max
};

再看这个问题爬楼梯问题,我们用dp思路考虑一下,

1
2
3
4
5
6
7
8
9
10
11
12
13
var so = function(n) {
var dp = [1, 2]
for(var i = 2; i < n; i++) {
dp[i] = dp[i-1] + dp[i-2]
}
console.log(dp)
}

so(10)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

so(100)
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676220, 23416728348467684, 37889062373143900, 61305790721611580, 99194853094755490, 160500643816367070, 259695496911122560, 420196140727489660, 679891637638612200, 1100087778366101900, 1779979416004714000, 2880067194370816000, 4660046610375530000, 7540113804746346000, 12200160415121877000, 19740274219868226000, 31940434634990100000, 51680708854858330000, 83621143489848430000, 135301852344706760000, 218922995834555200000, 354224848179262000000, 573147844013817200000]

选择问题,0或1,
如果有10个选择,最终有89条路,
如果有100个选择在你面前,有5x10^20条路,
全球有64x10^8个人,
妈呀算不过来了…😂
所以说世界上没有两片完全相同的叶子…
人生不到3w天
一天一个选择
那得有多少条路
哈哈哈哈哈😂 本来在写代码,写着写着写偏了
改天接着扯…