lcDP1 - 动态规划1

1 动态规划

从背包问题开始:

最重要的是,能够用dp数组,1到3维度一般,去表示最终结果,对于具体的题目,dp[i][j]表示什么意思,将成为解答的关键

很多动态规划都可以使用带记忆化的搜索去做

2 例题

0410splitArrayMinMax 分割出最小的子数组最大值

1 题目

https://leetcode-cn.com/problems/split-array-largest-sum/

2 解题思路

参考官方解答:https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode-solution/

  • 1 dp: 首先搞明白动态规划的单元,注意,不仅仅是说增加一个元素,对分割造成了什么影响,而且还要考虑,不通的分割数目,本题目是分割,那么一定是分割数目以及分割对象带来的变化为dp的状态迁移, dp[i][j] means: res of: nums[:i] to be splited in j’s segments, dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1},所以
  • 2 二分查找法:这样,判断一个数字能否作为分割m个子数组的方案?应该很好判断,顺序遍历即可
    • 2.1 那么记录该数字为x,最小就是数组里的最大值,最大即为数组和,于是仅仅需要用二分法,从这个范围中找出该数字即可
    • 2.2 具体如何二分?若x过于小了,会导致分割数目太大,然后我们就知道往大处搜索,反之同理
  • 3 二分法的标准写法:
    • 3.1 注意用>>代表除2,尤其是考虑负数时候有区别
    • 3.2 注意当往大地方搜,st = mid+1,往小地方则不用,不然可能导致ed漏搜索
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      bool lastCheck = false;
      while(st < ed) {
      x = (st + ed) >> 1; // means: floor of (st + ed)
      lastCheck = xIsLarge(x, nums, m);
      if(lastCheck) {
      ed = x; // when ed - st = 1, (st + ed) >> 1 == st
      } else {
      st = x + 1;
      }
      }
      return st;


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<int> preSum = { 0 };
for(int i = 0; i < n; ++i) {
preSum.push_back(preSum.back() + nums[i]);
}
// // dp[i][j] means: res of: nums[:i] to be splited in j's segments
// // dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1}
// vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX));

// dp[1][1] = nums[0];
// for(int i = 1; i <= n; ++i) {
// for(int j = 1; j <= min(m, i); ++j) {
// if(j == 1) {
// dp[i][1] = preSum[i] - preSum[0];
// continue;
// }
// int tmpMaxMin = 0;
// for(int k = j - 1; k < i; ++k) {
// tmpMaxMin = max(dp[k][j-1], preSum[i] - preSum[k]);
// dp[i][j] = min(dp[i][j], tmpMaxMin);
// }
// }
// }
// return dp[n][m];

// binsearch x as the min max res
int st = *max_element(nums.begin(), nums.end());
int ed = preSum[n];
int x = -1;


bool lastCheck = false;
while(st < ed) {
x = (st + ed) >> 1;
lastCheck = xIsLarge(x, nums, m);
if(lastCheck) {
ed = x; // when ed - st = 1, (st + ed) >> 1 == st
} else {
st = x + 1;
}
}

// at last, st == ed
return st;
}

bool xIsLarge(int x, vector<int>& nums, int m) {
int cnt = 1;
int curSum = 0;
for(int i = 0; i < nums.size(); ++i) {
if(curSum + nums[i] > x) {
++cnt;
curSum = nums[i];
} else {
curSum += nums[i];
}
}
// cout << ">> x/cnt is" << x << "/" << cnt << endl;
return cnt <= m;
}
};

0403frogCrossRiver 青蛙过河

1 题目

https://leetcode-cn.com/problems/frog-jump/

2 解题思路

  • 1 动态规划:首先明白动态规划最终是指向结果的,于是,定义dp[i][k],为到达i的最后一跳长度为k,是否能够跳到目的地
    • 1.1 首先有疑问:那k岂不是max(stone) - min(stone),那k就会非常大,不合理啊?错,因为每一跳长度最多增加1,然而你最多有n-1跳,于是 k <= n-1
    • 1.2 状态转移: dp[i][k] = dp[j][k] || dp[j][k-1] || dp[j][k+1],j就是i的上一跳,那么我们可以直到,j到i,k=stone[i] - stone[j]
    • 1.3 需要注意到上面的状态转移: 因为是从j跳,必须保证: k <= j+1,因为你从第j个石头开始跳,最远长度就是j+1
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
32
33
34
class Solution {
public:
bool canCross(vector<int>& stones) {
int n = stones.size();
// jump to i, and last jump dis
vector<vector<bool>> jump(n , vector<bool>(n, false));
jump[0][0] = true;

// the i th jump len <= i
for(int i = 1; i < n; ++i) {
if(stones[i] - stones[i - 1] > i) {
return false;
}
}

// dp, from j jump to i
bool res = false;
for(int i = 1; i < n; ++i) {
for(int j = 0; j < i; ++j) {
int k = stones[i] - stones[j];
// cout << j << " -> " << i << " 's dis: " << k << endl;
if(k > j + 1) {
continue;
}
// cout << jump[j].size() << " / " << k + 1 << " jump[j][k] || jump[j][k-1] || jump[j][k+1] " << jump[j][k] << jump[j][k-1] << jump[j][k+1] << endl;
jump[i][k] = jump[j][k] || jump[j][k-1] || jump[j][k+1];
if(i == n - 1 && jump[i][k]) {
res = true;
}
}
}
return res;
}
};

0488zumaGame 祖玛游戏

1 题目

https://leetcode-cn.com/problems/zuma-game/

2 解题思路

  • 1 对于hand中,每次挑选一个去填补到board中,然后消除board中的球,接着用剩下的hand再选择一个,到board里中去消除,dfs去遍历即可
  • 2 使用记忆化搜索 memo[board + “ “ + hand]记录了对应的board和hand的结果,为何” “是必须的?
    • 2.1 考虑以下例子:
    • 2.2 可以知道必须在中间的RR中先插入B,那么假设我们的第一次搜索从第一个字符G,第二个字符是B,开始,那么我们的memo中会有结果(若是不带空格):memo[RRYGGYYRBRYYGGYRRGGBB],这样当第一个字符变成B,我们会在memo发现一个失败的方法直接返回结果,导致改题变成没有结果,同时这个例子也解释了为何减枝的条件3需要在两个相同字符之间插入字符,如果带了空格,就能够绝对避免这个问题,因为:
    • memo[RRYGGYYRBRYYGGYRR GGB] 和 memo[RRYGGYYRBRYYGGYRR GGBB]就能够区分开

      “RRYGGYYRRYYGGYRR”

      “GGBBB”

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
public:
int allBallsCnt = -1;
map<string, int> memo;

int findMinStep(string board, string hand) {
// simulate this game
int res = 0;
allBallsCnt = hand.size();
res = bfs(board, hand);
return res == INT_MAX ? -1 : res;
}
int bfs(string board, string hand) {
// space mustn't be eliminated! it's neutig!
if(memo.find(board + " " + hand) != memo.end()) {
return memo[board + " " + hand];
}

if(0 == board.size()) {
return allBallsCnt - hand.size();
}
if(0 == hand.size()) {
return INT_MAX;
}

int useRes = INT_MAX;
string lastTarBallStr = "";
for(int k = 0; k < hand.size(); ++k) {
string nextHand = hand.substr(0, k) + hand.substr(k + 1);
string tarBallStr = hand.substr(k, 1);

// case1: cut the same ball
if(tarBallStr == lastTarBallStr) {
continue;
}

// use this char, find put pos
for(int i = 0; i <= board.size(); ++i) {
// case2: only insert at the start of str with same chars
if(i > 0 && board[i - 1] == hand[k]) {
continue;
}

// case3: only put when cur is equal current || when cur is not equal to two continuous same chars
if(i < board.size() && board[i] == hand[k] || \
i > 0 && board[i] == board[i-1] && hand[k] != board[i-1]) {
string tmpBoard1 = board;
tmpBoard1.insert(i, tarBallStr);
// reduce repeat balls
reduceRepeat(tmpBoard1);

// put to tarBall left and right
int lRes = bfs(tmpBoard1, nextHand);

useRes = min(lRes, useRes);
}
}

lastTarBallStr = tarBallStr;
}
memo[board + " " + hand] = useRes;
return useRes;
}

inline void reduceRepeat(string& board) {
int idx = 0;
// cout << "reducing " << board << endl;
while(board.length() > 0 && idx < board.length()) {
int st = idx, cur = st;
char head = board[st];
while(++cur < board.length() && board[cur] == head) {
}
if(cur - st >= 3) {
board.erase(st, cur - st);
idx = 0;
} else {
idx = cur;
}
}
// cout << "after redu " << board << endl;
}

};

0552checkRecord 学生出勤记录

1 题目

https://leetcode-cn.com/problems/student-attendance-record-ii/

2 解题思路

  • 1 初步思路 dp[i][j]作为直到i天,以j为出勤记录的所有记录数,但是会发现无法处理连续的L的情况
  • 2 更改,采用官方题解思路: dp[i][j]为以连续j个l为结尾的记录数,首先只考虑PL,但是此方法不行,因为,A可以隔断两个L,所以,如果先算出所有PL的方法,然后将A插入,那么结果一定会比用A去隔断两个L少。
  • 3 官方接单: dp[i][j][k]是含有j个A的k个L为结尾的记录数
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:

int bigInt = 1000000007;
int checkRecord(int n) {
if(n <= 2) {
return n == 1 ? 3 : 8;
}

// we can use A to interrupt the LLL, so we calculate A after only PL
// // n's day without 'A'
// vector<vector<long long>> dp(n + 1, vector<long long>(3, 0));

// // dp[i][j], j means end with n's L
// dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0;


// for(int i = 2; i <= n; ++i) {
// // end with p
// dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];

// // ent with l
// dp[i][1] = (dp[i - 1][0]) % bigInt;

// // end with ll
// dp[i][2] = dp[i - 1][1] % bigInt;
// cout << i << " th: P/L: " << dp[i][1] << " " << dp[i][0] << endl;
// }

// // when there is a A:
// long long res = 0;
// res += ((dp[n][0] + dp[n][1]) % bigInt + dp[n][2]) % bigInt;
// res += (((dp[n-1][0] + dp[n-1][1]) % bigInt + dp[n-1][2]) % bigInt * n) % bigInt;


// n's day without 'A'
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(2, vector<long long>(3, 0)));

// dp[i][j], j means end with n's L
dp[0][0][0] = 1;

for(int i = 1; i <= n; ++i) {
// end with p
for(int j = 0; j < 2; ++j) {
for(int k = 0; k <= 2; ++k) {
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % bigInt;
}
}

// end with a
for(int k = 0; k <= 2; ++k) {
dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k]) % bigInt;
}

// ent with l
for(int j = 0; j < 2; ++j) {
for(int k = 1; k <= 2; ++k) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k-1]) % bigInt;
}
}
}

int res = 0;

for(int j = 0; j < 2; ++j) {
for(int k = 0; k < 3; ++k) {
res = (res + dp[n][j][k]) % bigInt;
}
}


return res;
}
};

0600countUncontinous1 不含连续1的非负整数

1 题目

https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/

2 解题思路

  • 1 解题思路:
    • 1.1 很显然的动态规划,首先考虑问题: 给你一个二进制数字a = 2^n,判断从0到a有多少个数字不含有连续的两个1?动态规划即可:
      • dp[len][0] = dp[len - 1][1] + dp[len - 1][0];
      • dp[len][1] = dp[len - 1][0];
      • 其中dp[len][0]表示长度为len然后以0开始的二进制数字的集合中,含有多少个不连续为1的数字
    • 1.2 有了上述的思考,那么对于1024,32这种数字的解答就很显而易见了,比如32 = 100000,那么答案就是:首先假设最高位为0,然后res += dp[5][0] + dp[5][1],这是所有: 0xxxx和1xxxx组成的答案,但是32是6位数字,还需要加上32本身即可
    • 1.3 更近一步,对于a = 101010 和 b = 110000 这样的呢?
      • 以每一个1对结果的贡献来思考,从高位到低位这样去思考:
      • 首先拿a来说,我们看最高位,和32一样的解法,接下来我们找到下一个1,那么就是变成,找以前缀为10,后缀为 0xxx 的有多少种,那么动态规划直接找出来就行,那么为什么不是1xxx,因为1xxx加上前缀10可能就大于a了,就超出了范围,那么我们接着找到下一个1,也就是前缀为1010,找0x有多少种,然后最后找不到1,看看a本身是否合理加上即可
      • 对于b,首先第一个1对最终结果的贡献都是和32一样的,那么第二个1呢?很显然,遇到了连续的第二个1,意味着后面的1对答案都不会有贡献,因为以11为前缀的都是不合法的,所以仅仅需要考虑,将第二个连续的1变成0,以10为前缀,xxxx有多少中方案,很简单,就是 dp[4][0] + dp[4][1]
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
public:
int findIntegers(int n) {
int tmp = n;
int bit = -1;
vector<int> bits = {};

while(tmp > 0) {
bits.push_back(tmp & 1);
tmp = tmp >> 1;
}

int k = bits.size();
vector<vector<int>> dp(k, vector<int>(2, 0));

if(k <= 1) {
return 2;
}

dp[0][0] = 1; // mainly for the last bit is 1
dp[0][1] = 0;

dp[1][0] = 1;
dp[1][1] = 1;

for(int len = 2; len <= k - 1; ++len){
dp[len][0] = dp[len - 1][1] + dp[len - 1][0];
dp[len][1] = dp[len - 1][0];
// cout << "dp " << len << "/0,1 = " << dp[len][0] << "," << dp[len][1] << endl;
}

int lastOneBitIdx = k - 1;

// assume the biggest bit starts with 0
int res = dp[lastOneBitIdx][0] + dp[lastOneBitIdx][1];
// cout << "assume biggest bit = 0's res : " << res << endl;

bool mySelfOk = true;
while(lastOneBitIdx > 0) {
int nextOneBitIdx = lastOneBitIdx - 1;
cout << ">> last/next: " << lastOneBitIdx << "/" << nextOneBitIdx << endl;
cout << "bits[next] " << bits[nextOneBitIdx] << endl;

// find next one bit
while(bits[nextOneBitIdx] != 1) {
cout << "not 1 bit: " << nextOneBitIdx << endl;
-- nextOneBitIdx;
if(nextOneBitIdx == -1) {
return res + mySelfOk;
}
}

cout << "last/next: " << lastOneBitIdx << "/" << nextOneBitIdx << endl;
if(lastOneBitIdx - nextOneBitIdx < 2) {
// view the bits[nextOneBitIdx] as 0
res += dp[nextOneBitIdx][0] + dp[nextOneBitIdx][1];
mySelfOk = false;

// cout << "+ dp " << nextOneBitIdx << "," << 0 << " break!!!" << endl;
break;
} else {
// view the bits[nextOneBitIdx] as 0
res += dp[nextOneBitIdx][0] + dp[nextOneBitIdx][1];
lastOneBitIdx = nextOneBitIdx;
// cout << "+ dp " << nextOneBitIdx << "," << 0 << endl;
// cout << "lastOneBitIdx is " << lastOneBitIdx << endl;
// cout << "curRes = " << res;

}
}

cout << "me ok: " << mySelfOk << endl;

return res + mySelfOk;
}
};