算法-动态规划优化

前言

最近总是在断断续续的看动态规划相关的算法题,总感觉对于动态规划这个东西需要仔细琢磨一下,在本子上写写画画才能计算出 边界条件状态转移方程,而这其中最难的就是状态转移方程。
所以今天这篇文章的核心也就是 基础状态转移方程状态转移方程的优化

动态规划简介

动态规划就是把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。同时动态规划是自底向上求解,通过循环来从最基础已知的答案逐步求解到想要的答案。


开篇

我想大部分人在初次学习 动态规划 的时候,做的第一道题目肯定都是基础 斐波那契数列,而斐波那契数列的解题答案中就有很多的版本,例如 递归数组动态优化

递归

1
2
3
4
5
6
public int Fibonacci(int n) {
if (n == 0 || n == 1) {
return n;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}

动态规划

1
2
3
4
5
6
7
8
9
10
// 动态规划 -> 本次的计算结果有前两个相加而得
public int Fibonacci(int n) {
int[] arrs = new int[40];
arrs[0] = 0;
arrs[1] = 1;
for (int i = 2; i <= n; i++) {
arrs[i] = arrs[i-1] + arrs[i-2];
}
return arrs[n];
}

动态规划优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 动态规划优化
* 时间复杂度: O(n)
* 空间复杂度: O(1)
*/
public int Fibonacci(int n) {
if (n <= 1) {
return n;
}
int one = 0;
int two = 1; // 只存储最近使用的两位位数 n(two) / n-1(one)
int temp = 0;
for (int i = 2; i < n; i++) {
temp = two;
two = one + two;
one = temp;
}
return two+one;
}

在动态规划优化中,我们通过仅保存每次求解所需的值,这样可以将原来的空间复杂度由 O(n) 降到 O(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
/**
* 动态规划
* 状态转移方程: dp[i][j] = s1.chatAt(i) == s2.charAt(j) && dp[i-1][j-1]
* 时间复杂度: O(m*n)
* 空间复杂度: O(m*n)
*/
public String LCS (String str1, String str2) {
int[][] dp = new int[str1.length()+1][str2.length()+1];
int max = 0; // 最大长度
int position = 0; // 坐标

for (int i = 1; i < str1.length()+1; i++) {
for (int j = 1; j < str2.length()+1; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > max) {
max = dp[i][j];
position = j;
}
}
}
}

return max == 0 ? "-1" : str2.substring(position-max, position);
}

动态规划优化

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
/**
* 动态规划
* 状态转移方程: dp[i % 2][j] = s1.chatAt(i) == s2.charAt(j) && dp[i % 2 == 0 ? 1 : 0][j-1]
* 时间复杂度: O(m*n)
* 空间复杂度: O(m*2)
*/
public String LCS (String str1, String str2) {
// write code here
int l = str1.length() > str2.length() ? str1.length() : str2.length();
int[][] dp = new int[2][l+1];
int max = 0; // 最大长度
int position = 0; // 坐标

for (int i = 1; i < str1.length()+1; i++) {
for (int j = 1; j < str2.length()+1; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
// 获取上一层节点的值
dp[i%2][j] = dp[i%2 == 0 ? 1 : 0][j-1] + 1;
if (dp[i%2][j] > max) {
max = dp[i%2][j];
position = j;
}
} else {
dp[i%2][j] = 0; // 不相等
}
}
}

return max == 0 ? "-1" : str2.substring(position-max, position);
}

在这个版本的优化中,通过以往的使用特点,当前节点的值只与上一层的节点值有关。因此最后的优化就在于存储本行数据和上一行数据,这样在计算 dp[i][j] 仅可以通过上一层数据即可获得值。


总结

做题的时候目光可以只在一道题上,但是当你做完了题,就需要将目光放在全局纵览,这样你才能获得更多的知识。


个人备注

此博客内容均为作者学习所做笔记,侵删!
若转作其他用途,请注明来源!