动态规划（一）
动态规划是解决什么问题的？
动态规划一般是解决求最值的问题，一般求最值中会出现“重复的子问题”，核心就是穷举，然后筛选出来想要的答案。常用的筛选有MAX或者MIN等常见的最值函数。
动态规划的优化方法
前面说到了重叠子问题这个名词，对算法稍微有感觉的话会立刻想到“斐波那契数列”这个经典的问题，他就是由若干个子问题不断递归形成的问题，这里就拿斐波那契数列举例子吧。
下面用常规的写法写一下斐波那契数列问题。
1
2
3
4
5
6
7
8
9
10
11
| class example{
public static void main(String [] args){
int N = 999;
System.out.println(fib(N));
}
public static long fib(int N){
if( N==0 ) return 0;
if( N==1 || N==2 ) return 1;
return fib(N-1)+fib(N-2);
}
}
|
这是极为常规的写法，锁定递归最基本的情况，然后直接递归回去即可。
但是我们能够发现，在运算的过程中，每两个递归都会重复运算一个数，这个数都要被后面的递归慢慢计算，性能损失很大。因此，我们不妨新增一个新的“备忘录”去记载已经计算过的数字。那么我们的代码可以有下面的优化：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class example {
public static long[] dp = new long[10000];
public static void main(String[] args) {
int N = 999;
System.out.println(fib(N));
}
public static long fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
if (dp[N] != 0) return dp[N];
dp[N] = fib(N - 1) + fib(N - 2);
return dp[N];
}
}
|
这样的话，我们就把每一次计算的值保留了下来，避免重复多次计算，需要的时候直接取出即可。
上面的算法都是利用了递归的思想，是反向操作（自底向上）的方法，我们也可以使用for循环进行操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class example {
public static long[] dp = new long[10000];
public static void main(String[] args) {
int N = 999;
System.out.println(fib(N));
}
public static long fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
long before1 = 1;
long before2 = 1;
long curr = 0;
for (int i = 3; i <= N; i++) {
curr = before1 + before2;
before1 = before2;
before2 = curr;
}
return curr;
}
}
|
这样的话就可以达到内存和性能双赢的局面了。
凑零钱问题
Leetcode：https://leetcode.cn/problems/coin-change/
分析一下这个题目：如果给出我们1元、3元、5元这三种硬币，让我们凑出来10元钱，试问我们应该如何操作呢？我们不妨这样想：
- 10 = 1 + 9
- 10 = 3 + 7
- 10 = 5 + 5
下面我们就把问题化解为9元、7元、5元最少需要多少枚硬币的问题了，显然这是一个可以进行递归的问题，这样我们就找到了这其中的套路，剩下的只需要将比较这三种情况的“局部最小值”，然后得出总体最小值，这样就可以完美的解决这个问题了。
我们把我们的核心代码写出来，做个伪代码的框架：
1
2
| for coin in coins:
result = mon(result,1+dp(n-coin))
|
这样的话，我们核心的框架就已经建立起来了，下面依旧是定义基本情况，这里我们定义 dp[N]是N元所对应的硬币数量，那么我们只有一种基本情况：dp[0]=0，除此之外的其他情况都可使用这个条件推导出来。下面直接上代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class example{
public static int coinChange(int[] coins,int amount){
int[] dp = new int[amount+1];
for(int i = 0; i<amount+1; i++){
dp[i]=amount+1;
}
dp[0]=0;
for(int n=0; n<amount+1;n++){
for(int coin : coins){
if(n-coin<0)continue;
dp[n]=Math.min(dp[n],1+dp[n-coin]);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
|
最长子序列问题
名词解释：子序列是指可以不连续，但是要按顺序的一个字符串，子串要求连续。
LeetCode：https://leetcode.cn/problems/longest-increasing-subsequence/
思路和之前差不多，我们也是一样，定义一个dp[N]用于存储第N+1个数字的最长子序列数目，然后只需要不断地和前一个比他小的数衔接即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int [nums.length];
int res = 0;
for(int i = 0; i<nums.length;i++){
int before = 0;
for(int j = i-1; j >= 0; j--){
if(nums[j] < nums[i]){
before = Math.max(dp[j],before);
}
}
dp[i] = Math.max(dp[i],before+1);
res = Math.max(res,dp[i]);
}
return res;
}
}
|
子序列问题变种：俄罗斯套娃信封
LeetCode：https://leetcode.cn/problems/russian-doll-envelopes/
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
| class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes.length == 0) {
return 0;
}
int[] tmp = new int[envelopes.length];
int n = envelopes.length;
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] e1, int[] e2) {
if (e1[0] != e2[0]) {
return e1[0] - e2[0];
} else {
return e2[1] - e1[1];
}
}
});
for(int i = 0; i<envelopes.length;i++){
tmp[i]=envelopes[i][1];
}
return lengthOfLIS(tmp);
}
public static int lengthOfLIS(int[] nums) {
int[] dp = new int [nums.length];
int res = 0;
for(int i = 0; i<nums.length;i++){
int before = 0;
for(int j = i-1; j >= 0; j--){
if(nums[j] < nums[i]){
before = Math.max(dp[j],before);
}
}
dp[i] = Math.max(dp[i],before+1);
res = Math.max(res,dp[i]);
}
return res;
}
}
|
看着这个算法人畜无害的，但是实际上你运行起来就会发现他会超时！用官方的解答来看，是利用了二分法来提高效率实现的这个算法。后面再说到二分法的时候在详细说说吧！
