Skip to content

Commit 21f8f56

Browse files
awangdevawangdev
committed
dp, range dp
1 parent 51c231f commit 21f8f56

18 files changed

Lines changed: 1474 additions & 943 deletions

‎Java/Burst Balloons.java‎

Lines changed: 38 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,36 @@
11
H
2-
1518586276
3-
tags: Divide and Conquer, DP
2+
1522042382
3+
tags: Divide and Conquer, DP, Range DP, Memoization
44

5-
Range DP.
6-
因为数组规律会变, 所以很难找'第一个burst的球'. 反之, 想哪一个是最后burst?
7-
最后burst的那个变成一堵墙: 分开两边, 分开考虑, 加法原理; 最后再把中间的加上.
5+
一排球, 每个球有value, 每次扎破一个, 就会积分: 左*中间*右 的值. 求, 怎么扎, 最大值?
86

9-
Range DP 三把斧:
10-
1. 中间劈开
11-
2. 砍断首或尾
12-
3. Range区间作为iteration的根本
7+
TODO: Need more thoughts on why using dp[n + 2][n + 2] for memoization, but dp[n][n] for range DP.
138

14-
Note: print the process. use pi[i][j] and print recursively.
15-
Print k, using pi[i][j]: max value taken at k
9+
#### Range DP
10+
- 因为数组规律会变, 所以很难找'第一个burst的球'. 反之, 想哪一个是最后burst?
11+
- 最后burst的那个变成一堵墙: 分开两边, 分开考虑, 加法原理; 最后再把中间的加上.
12+
- dp[i][j] represent max value on range [i, j)
13+
- Need to calculate dp[i][j] incrementally, starting from range size == 3 ---> n
14+
- Use k to divide the range [i, j) and conquer each side.
1615

16+
##### Range DP 三把斧:
17+
- 中间劈开
18+
- 砍断首或尾
19+
- Range区间作为iteration的根本
1720

18-
其实会做之后挺好想的一个DP。
19-
dp[i][j] = balloons i~j 之间的sum. 然后找哪个点开始burst? 设为x。
20-
For loop 所有的点作为x， 去burst。
21-
每次burst都切成了三份：左边可以recusive 求左边剩下的部分的最大值 + 中间3项相乘 + 右边递归下去求最大值。
21+
##### Print the calculation process
22+
- use pi[i][j] and print recursively.
23+
- Print k, using pi[i][j]: max value taken at k
2224

25+
#### Memoization
26+
- 其实会做之后挺好想的一个DP
27+
- dp[i][j] = balloons i~j 之间的 max.
28+
- 然后找哪个点开始burst? 设为x。
29+
- For loop 所有的点作为x， 去burst。
30+
- 每次burst都切成了三份：左边可以recusive 求左边剩下的部分的最大值 + 中间3项相乘 + 右边递归下去求最大值。
31+
- Note: 这个是Memoization, 而不纯是DP
32+
- 因为recursive了，其实还是搜索，但是memorize了求过的值，节省了Processing
2333

24-
这个是momorization, 而不纯是DP
25-
因为recursive了，其实还是搜索，但是memorize了求过的值，节省了Processing
2634

2735
```
2836
/*
@@ -56,17 +64,20 @@
5664

5765
/*
5866
Thoughts:
59-
Range DP. Think about it: it's really hard to find which ballon burst first; how about which ballon burst last?
67+
Range DP. Think about it: it's really hard to find which ballon burst first;
68+
how about which ballon burst last?
69+
6070
If it burst last, the value will be left * lastItem * right.
61-
Now we just have to pick which one burst last? k = [i, j]
71+
Now we just have to pick which one burst last? k in [i, j]
72+
6273
Note that, we need the invisible wall on head and tail, so make sure creating dp at length of n+2
63-
dp[i][j] represents the max value for range (i + 1 ~ j - 1)
74+
dp[i][j] represent max value on range [i, j)
6475
6576
Pick k in the middle:
6677
dp[i][j] = dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j];
6778
where:
68-
dp[i][k]: range (i + 1, k - 1)
69-
dp[k][j]: range (k + 1, j - 1)
79+
dp[i][k]: range (i, k)
80+
dp[k][j]: range (k, j)
7081
7182
Time O(n^3)
7283
Space O(n^2)
@@ -77,16 +88,16 @@ public int maxCoins(int[] nums) {
7788
return 0;
7889
}
7990
int n = nums.length;
80-
8191
int[] values = new int[n + 2];
82-
values[0] = values[n + 1] = 1;
92+
values[0] = 1;
93+
values[n + 1] = 1;
8394
// reassign new array
8495
for (int i = 1; i <= n; i++) {
8596
values[i] = nums[i - 1];
8697
}
8798

88-
n = values.length; // increase n size and simplify code below
89-
int[][] dp = new int[n][n];
99+
n = values.length;
100+
int[][] dp = new int[n][n]; // dp[i][j] denotes the max value in range [i, j)
90101
// Critical: iterate over RANGE: then come up with i and j; i <= n - len
91102
for (int len = 3; len <= n; len++) {
92103
for (int i = 0; i <= n - len; i++) {
@@ -96,6 +107,7 @@ public int maxCoins(int[] nums) {
96107
}
97108
}
98109
}
110+
99111
return dp[0][n - 1];
100112
}
101113
}

‎Java/Largest Rectangle in Histogram.java‎

Lines changed: 34 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,14 @@
11
H
22
1520813180
3-
tags: Array, Stack
3+
tags: Array, Stack, Monotonous Stack
4+
5+
给n个bar,组成柱状图histogram. 求在这一排柱状图里面可以找到的面积最大的长方形.
6+
7+
思考: 找长方形面积, 无非是找两个index, 然后底边长度 * height.
48

59
#### Monotonous Stack
6-
重点是根据找Histogram里面rectangle的性质, 维持一个单调递增的Stack
7-
在loop over indexes的时候:
10+
- 重点是根据找Histogram里面rectangle的性质, 维持一个单调递增的Stack
11+
- 在loop over indexes的时候:
812
- 如果高度>= previous peek(), 那么对于那个peek, 就意味着, 往下走, 一直走高嘛, 之前的peek总可以继续抄底
913
- 什么时候不能抄底了呢? 就是有一个下降趋势的时候
1014
- 这时候并不是calculate所有前面的peek, 而是考虑 大于 current height的之前所有的peek.
@@ -72,4 +76,31 @@ public int largestRectangleArea(int[] heights) {
7276
return max;
7377
}
7478
}
79+
80+
81+
/**
82+
* @param {number[]} heights
83+
* @return {number}
84+
*/
85+
// javascript version
86+
var largestRectangleArea = function(heights) {
87+
if(heights == null || heights.length == 0) {
88+
return 0;
89+
}
90+
let n = heights.length;
91+
let max = 0;
92+
let stack = []; // use it as stack, with index 0 being the top
93+
for (let i = 0; i <= n; i++) {
94+
let currHeight = i == n ? -1 : heights[i];
95+
while (stack.length > 0 && currHeight <= heights[stack[0]]) {
96+
let currPeekHeight = heights[stack[0]];
97+
stack.splice(0, 1);
98+
let width = stack.length == 0 ? i : i - stack[0] - 1;
99+
max = Math.max(max, currPeekHeight * width);
100+
}
101+
stack.unshift(i);
102+
}
103+
104+
return max;
105+
};
75106
```

‎Java/Nim Game.java‎

Lines changed: 50 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,41 @@
11
E
2+
1522047752
3+
tags: Brainteaser, DP, Game Theory
24

3-
著名Nim游戏。
4-
写一些，发现n=4,5,6,7,8...etc之后的情况有规律性: 谁先手拿到4就输了.
5-
最终很简单n%4!=0就可以了
5+
#### Brainteaser
6+
- 著名Nim游戏
7+
- 写一些，发现n=4,5,6,7,8...etc之后的情况有规律性: 谁先手拿到4就输了.
8+
- 最终很简单n%4!=0就可以了, time, space O(1)
9+
10+
#### DP
11+
- 正规地找规律做, 就跟 coins in a line 一样, 按照先手后手来做
12+
- 可以rolling array 优化空间
13+
- Time O(n), 当然啦, 这个题目这样会timeout, 可以使用brainteaser的做法写出结果.
614

715
```
816
/*
9-
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
17+
You are playing the following Nim Game with your friend:
18+
There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones.
19+
The one who removes the last stone will be the winner.
20+
You will take the first turn to remove the stones.
1021
11-
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
22+
Both of you are very clever and have optimal strategies for the game.
23+
Write a function to determine whether you can win the game given the number of stones in the heap.
1224
13-
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
25+
For example, if there are 4 stones in the heap,
26+
then you will never win the game: no matter 1, 2, or 3 stones you remove,
27+
the last stone will always be removed by your friend.
1428
1529
Hint:
1630
17-
If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?
31+
If there are 5 stones in the heap, could you figure out a way to remove the stones
32+
such that you will always be the winner?
1833
1934
2035
Hide Similar Problems (M) Flip Game II
2136
2237
*/
2338

24-
2539
/*
2640
Thoughts:
2741
If n = 4, we can do the following:
@@ -45,4 +59,32 @@ public boolean canWinNim(int n) {
4559
return n % 4 != 0;
4660
}
4761
}
62+
63+
64+
65+
/*
66+
Thoughts:
67+
Game theory DP. Consider the last step:
68+
for 1st player to win, the opponent needs to have the possibility to lose
69+
(assume 1st player take the chance when seeing one)
70+
71+
Make dp[i] represents true/false 1st will win, if given i stones.
72+
dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
73+
74+
return dp[n - 1]
75+
*/
76+
class Solution {
77+
public boolean canWinNim(int n) {
78+
if (n <= 3) {
79+
return true;
80+
}
81+
boolean[] dp = new boolean[3];
82+
dp[0] = dp[1] = dp[2] = true;
83+
for (int i = 3; i < n; i++) {
84+
dp[i % 3] = !dp[(i - 1) % 3] || !dp[(i - 2) % 3] || !dp[(i - 3) % 3];
85+
}
86+
return dp[(n - 1) % 3];
87+
}
88+
}
89+
4890
```

‎Java/Stone Game.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22
NOT DONE YET
33
```
44
/*
5-
There is a stone game.At the beginning of the game the player picks n piles of stones in a line.
5+
There is a stone game. At the beginning of the game the player picks n piles of stones in a line.
66
77
The goal is to merge the stones in one pile observing the following rules:
88

0 commit comments

Comments
 (0)