前言
最近总是在断断续续的看动态规划相关的算法题，总感觉对于动态规划这个东西需要仔细琢磨一下，在本子上写写画画才能计算出 边界条件 和 状态转移方程，而这其中最难的就是状态转移方程。
所以今天这篇文章的核心也就是 基础状态转移方程 和 状态转移方程的优化。
动态规划简介
动态规划就是把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。同时动态规划是自底向上求解，通过循环来从最基础已知的答案逐步求解到想要的答案。
开篇
我想大部分人在初次学习 动态规划 的时候，做的第一道题目肯定都是基础 斐波那契数列，而斐波那契数列的解题答案中就有很多的版本，例如 递归、 数组 和 动态优化。
递归
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
|
public int Fibonacci(int n) {
if (n <= 1) {
return n;
}
int one = 0;
int two = 1;
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
|
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
|
public String LCS (String str1, String str2) {
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] 仅可以通过上一层数据即可获得值。
总结
做题的时候目光可以只在一道题上，但是当你做完了题，就需要将目光放在全局纵览，这样你才能获得更多的知识。
个人备注
此博客内容均为作者学习所做笔记，侵删！
若转作其他用途，请注明来源！