有人相爱，有人看海，有人dp做不出来
初入DP
Fibonacci
Leetcode-斐波那契
通过计算前面的一些项来得出序列中的指定项的值，即递推。一个比较熟悉的例子即斐波那契数列。
我们知道斐波那契数列有$f(n-1)+f(n)=f(n+1)$，即
对于该数列，他的每一项都是由他的前两项推出的，构成了一个递推序列。类似这样的问题便可以用动态规划的思想解决。
动态规划就是通过拆分问题，定义问题状态和状态之间的关系（ 如上面的f(n),f(n-1),f(n+1)之间的关系），使得问题能够以递推（或者说分治）的方式去解决。
实际上，递推是一种最简单的状态转移。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int fib(int n) {
int[] f = new int[31];
f[0] = 0;
f[1] = 1;
for(int i=2;i<=n;i++){
f[i] = f[i-1]+f[i-2];
}
return f[n];
}
}
|
使用一个长度为31的数组f来存储Fibonacci数列的值。由于Fibonacci数列的定义，可以直接设置f[0] = 0和f[1] = 1。
接下来，从第2个位置开始循环计算数组中其他位置的值，直到计算到第n个位置。在每个位置上，都将该位置的值设置为前两个位置的值之和，即
$$f[i] = f[i-1] + f[i-2]$$
最后，该方法返回数组中第n个位置的值，即Fibonacci数列的第n个数。
通过这个例子，我们大概知道了动态规划是一种怎样的算法。他包含以下几个要点
- 定义状态：问题的状态表示具有特定含义的变量集合，它们描述了问题的局面和某些属性，通常使用一个或多个变量来表示问题的状态。
- 定义状态转移方程：状态转移方程描述了相邻两个状态之间的关系，以及如何从前一个状态转移到后一个状态。通常通过递推或者其他方式，将问题拆分成小的子问题，并使用已经解决的子问题的解来推导出当前问题的解。
- 定义初始状态：初始状态是最小的问题实例的解，它是递推或者其他方式的起点，通过递推或者其他方式，逐步推导出较大问题的解。
爬楼梯
Leetcode-爬楼梯
1
2
3
| 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
|
1
2
3
4
5
6
7
8
| 例
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
|
首先，由于每次只能爬1或2节台阶
则对于每一节台阶，从地面(0)到当前台阶(n)的总方案数为当前台阶的前1，2节台阶爬楼梯方案数之和。
则只需要对斐波那契代码稍作改造，有
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int climbStairs(int n) {
int[] f = new int[31];
f[0] = 1;
f[1] = 1;
for(int i=2;i<=n;i++){
f[i] = f[i-1]+f[i-2];
}
return f[n];
}
}
|
这里对初始值做了改变，f(n)为从0到当前台阶的总方案数，则有f(0)和f(1)均为1。
通过这两个例子可以知道，同一个问题是可以有不同问法的，但解法是相同的。类似这样的递推即最简单的动态规划了。
使用最小花费爬楼梯
动态规划不仅是求方案数的好方法，也非常适合用来求最值
Leetcode-使用最小花费爬楼梯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
|
显然这道题是上题的进阶，同样的我们可以选择向上爬一个或者两个台阶，那么某层台阶的状态就和其前一层，二层相关。在这道题中我们要考虑到是花费，设f(n)为爬到当前台阶的最小花费，则有两种情况：
- 从前一层台阶n-1向上爬，花费为cost[n-1]，已支出为f(n-1)
- 从前二层台阶n-2向上爬，花费为cost[n-2]，已支出为f(n-2)
求最小花费，则许村取二者中的较小值，因此有
$$f[n]=min(f[n-1]+cost[n-1]，f[n-2]+cost[n-2])$$
得到爬到第n层的最小花费。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] f = new int[1001];
f[0] = 0;
f[1] = 0;
int n = 2;
for(;n<=cost.length;n++){
f[n]=Math.min(f[n-1]+cost[n-1],f[n-2]+cost[n-2]);
}
return f[n-1];}
}
|
以上，可以说是动态规划的入门了。
对于动态规划问题，大致流程就是
- 设计状态
- 状态转移方程
- 设定初始状态
- 执行状态转移
- 返回
接下来的每道题都将会是这个模式，尽管他们可能不再简单。
上一台阶
最大字数组和
1
2
3
4
5
6
7
8
9
10
| 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
|
- 设计状态
- 状态转移方程
- 设定初始状态
- 执行状态转移
- 返回
日常
2023/04/27 每日一题
Leetcode-最长字符串链
1
2
3
4
5
6
7
8
9
10
11
12
13
| 给出一个单词数组 words ，其中每个单词都由小写英文字母组成。
如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。
例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。
从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
示例
words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]
|
Q1 如何判断一个字符串是不是另一个字符串的前身？
对于前身，必有**前身的长度加1等于字符串长度。
遍历两个字符串，若某位置上字符相等，指针同时移动，不相等则只移动较长字符串的指针，当前身字符串指针走到串尾，判断较长字符串指针是否也走到了串尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private boolean isContain(String cur,String pre){
if(cur.length()!=pre.length()+1){
return false;
}
int i = 0;
int j = 0;
while(i<cur.length()&&j<pre.length()){
if(cur.charAt(i) == pre.charAt(j)){
i++;
j++;
}else{
i++;
}
}
return j == pre.length();
}
|
Q2 为什么是动态规划
在这个问题中，最长的字符串链一定是由若干个长度递增的字符串组成的，这些字符串之间具有前后顺序关系。因此，可以将问题划分为一个个子问题，即以每个字符串为结尾的最长字符串链。由于子问题之间具有重叠性，因此可以采用动态规划的方法来求解。
由此，我们设dp[i]为以字符串i为结尾的最长字符串链的大小。通过以下代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int longestStrChain(String[] words) {
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length()-o2.length();
}
}
);
int res = 0;
int[] dp = new int[words.length];
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < i; j++) {
if (isContain(words[i], words[j])) {
dp[i] = Math.max(dp[j]+1,dp[i]);
res = Math.max(res,dp[i]);
}
}
}
return res;
}
|
在这个问题中，可以遍历每个字符串 words[i]，并在之前的字符串 words[j]中查找是否有 words[j]为 words[i]的前身。
如果存在这样的字符串，那么可以将以字符串 words[j]结尾的最长字符串链的长度加 1，得到以字符串 words[i] 结尾的最长字符串链的长度 dp[i]，并与dp[i] 本身的值取最大值。因此，有状态转移方程
$$
if(contains(words[i], words[j]))\
\quad dp[i] = Math.max(dp[i], dp[j] + 1);
$$
最后找到所有状态 dp[i] 中的最大值，即为最长字符串链的长度。
不同路径
Leetcode-不同路径
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
| 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109
|
显然，一个格子的路径数等于其左边格子的路径数加上其上边格子的路径数。想到dp：
设dp[i][j]为到达i,j的路径数，那么有状态转移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
- 初始
dp[0][0] = 1
- 转移方程
dp[i][j] = dp[i-1][j] + dp[i][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
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
| ```
```javascript
window.unitCount = $(".ncells h4").index($(".currents")) + 1;
window.unit = $(".ncells h4").length;
function main(){
const frameObj = $("iframe").eq(0).contents().find("iframe.ans-insertvideo-online");
const videoNum = frameObj.length;
if(videoNum > 0){
console.log("%c当前小节中包含 " + videoNum + " 个视频","color:#FF7A38;font-size:18px");
var v_done = 0;
addEventListener("playdone" ,()=>{
v_done++;
if(v_done > videoNum){
} else if(v_done < videoNum){
watchVideo(frameObj, v_done)
} else {
console.log("%c等待跳转至下一小节...","font-size:18px");nextUnit();
}
});
watchVideo(frameObj, v_done);
} else {
if(window.unitCount < window.unit){
console.log("%c跳转至下一节","font-size:18px");
nextUnit();
} else {
console.log("%c好","color:red;font-size:18px");
}
}
}
function watchVideo(frameObj, v_done){
var playDoneEvent = new Event("playdone");
var v = undefined;
v = frameObj.contents().eq(v_done).find("video#video_html5_api").get(0);window.a = v;
try{ v.playbackRate = 8;}
catch(e){console.error("倍速设置失败"+e); nextUnit(); return;}
v.play();
console.log("%c正在 " + v.playbackRate + " 倍速播放第 " + (v_done + 1) + " 个视频","font-size:18px");
window.inter = setInterval(()=>{
v = window.a;
if(v.currentTime >= v.duration){
dispatchEvent(playDoneEvent);
clearInterval(window.inter);
}
if(v.paused){
v.play();
}
},1000);
}
function nextUnit(){
console.log("%c即将进入下一节...","color:red;font-size:18px");
setTimeout(() => {
$(document).scrollTop($(document).height()-$(window).height());
$(".orientationright").click();
console.log("%c下一节","color:red;font-size:18px");
if(window.unitCount++ < window.unit){ setTimeout(() => main(), 10000) }
}, 6000);
}
console.log("%c %c %d %c个小节，当前%c第%d小节 %c-chao", "color:#6dbcff", "color:red", window.unit, "color:#6dbcff", "color:red", window.unitCount, "font-size:8px");
main();
|
