leetcode-53 DP is insteresting
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 | /** |
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 | var maxSubArray = function(A) { |
We can also reduse the complexity of space.
1 | /** |
再看这个问题爬楼梯问题,我们用dp思路考虑一下,1
2
3
4
5
6
7
8
9
10
11
12
13var 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天
一天一个选择
那得有多少条路
哈哈哈哈哈😂 本来在写代码,写着写着写偏了
改天接着扯…