再谈动态规划

---

动态规划算法是很常见的，但是上次讲的那啥动态规划讲的几个例子都不是非常的经典，不过他们依旧都是动态规划。可以很清楚的看到他们都是利用了一个类似递归的表达式（状态转换式），从一个子问题的解到另一个子问题的解。如何能一眼看出这个使用的是动态规划算法，如何一眼看出状态转换式，这个可以说是非常困难的，需要对动态规划算法非常的熟悉才行。现在就来举几个之前写好了的例子来看看动态规划算法吧。

动态规划题目

最大路径和

这道题口头叙述起来比较困难，直接图形化描述吧。
  1
 3 2
2 4 7
上面有一个三角形形状的数阵。我们从第一层开始走到最后一层，每次到下一层只能选择向左或者向右，请问如何走才能使得最终走的路径上的数字之后是最大的。

思路分析

这个也是动态规划算法吗？这个当然是。先想想这个问题的子问题到底是什么？我们要知道走到第三层路径的最大的和，假如我们已经知道第二层的最大路径的和呢？

这有啥用，我们也不知道其他的位置怎么样，比如上面的那个第二层的最大路径和是4，但是要找到三层的最大路径要走旁边的那个2，所以说我们知道最大路径和是没用的。

但是我们可以考虑到每一层的每一个点的最大路径的值，最终的结果也就是最后一层的值的最大值。

 4 3
2 3 7

这是我们已经知道了第二层的每个点的最大路径值，那么第三层和第二层之间有什么联系呢？

比如第一个2，他只能和4加，那就是6,。

3可以选择和4或3加，去最大值就是7。

7只可以和3加，那就是10

6 7 10

最后我们找到最后一层的最大值，也就是10。这就是最大路径和。

那么状态转移式该如何写呢？

f(i, j) = max(f(i-1, j-1), f(i-1, j)) + f(i, j)；

当然这里的i,j都是有条件的。i的含义是第几层，j的含义的第几个。这样我们就可以使用二维数组来表示这个了

1 
3 2 
2 4 7

但是这样是否最优呢？我们可以轻易的发现，每次我们只是使用了一层的数据。比如找第三层的我们只需要第二层，找第四层我们只需要第三层，那么我们可不可以只使用一个一维数组来表示呢？

我们现在有个思路就是从最后一层开始算，为什么呢？因为到点是固定的。第一层只有一个值，最终得到的最大路径肯定是一维数组的第一个数，而且也不用考虑左右的问题了。

2 3 7
4 3
1
这是一个二维数组
找一个一维数组将最后一排赋给它
2 3 7
和第二排比较
——————
2 3 7
3 2   -> 6 9 7 只是变了第一个数和第二个数
和第一层比较
----
6 9 7
1     -> 10 9 7 这是变了第一个数，而这个第一个数就是最大路径

这个想法确实是蛮巧妙的。我感觉牛逼！！

这是状态转移方程就改变了

maxNum(j) = max( maxNum(j), maxNum(j+1) ) + f(i)(j)

这里的maxNum就是之前的那个一维数组。到最后这个数组的第一个数肯定就是最大路径和。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 10
int n = 0;
int maxSum[MAX] = {0};
int num[MAX][MAX] = {0};

int main(){
    cout<<"Please input n:";
    cin >> n;
    for (int i=0; i<n ;i++){
        for (int j=0; j<=i; j++){
            cin >> num[i][j];
        }
    }

    // 把最后一排赋给那个一维数组
    for (int i=0; i<n; i++){
        maxSum[i] = num[n-1][i];
    }

    for (int i = n-2; i>=0; --i){
        for (int j=0; j <=i; ++j){
            maxSum[j] = max(maxSum[j], maxSum[j+1]) + num[i][j];
        }
    }
    cout<<maxSum[0];
    return 0;
}

代码说明：

其实思路分析那一块，我做的说明已经足够多了，这里就稍微说一点吧。其实也就只有for循环那一块了吧。

第一个for循环指的是从倒数第二行开始，一直比到第一行(上面我们也是这么说的，倒着来比较)

第二个for循环是计算一位数组里的值，下面也用到了我们说的状态转移方程。

线性模型 过桥

---

/*  动态规划算法的线性模型
 * 【例题1】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，
 * 每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，
 * i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
 */

思路分析

这个题目其实蛮难的，说实话不容易想到。不过要说这个是动态规划的话，我们就要找子问题。第n个人过河，和第n-1个人过河到底有没有联系？好像并没有什么联系,每个人过桥的 时间都是乱的。但是假如我们把每个人过桥的时间给从大到小排个序呢？

这时候加了一个时间最大的人，该如何选择过河方案？

首先我们得让那n-1个人过河，然后派时间最少的人去河对面接那个后来的人。但是这样子的时间是不是最短的呢？肯定是的，就算你让后来的那个人代替倒数第二个人也是时间最短，因为他们始终只是过河过了一次，他们时间慢的人是不可以回头去接对面的人过来的。所以我们就得到了状态转移方程

f(i) = f(i-1) + 2*time[0] + time[i]

但是还有一个问题，这也就是这个问题难的地方。我难道不可以让n-2个人先过河，然后再让2个人过河。

这样的时间又如何呢？易得他们的状态转移方程

f(i) = f(i-2) + time[0] + time[i] + 2*time[1]

这个状态转移方程也是要说明一点的。首先我们要让最快的那个人把灯送回去，然后让最后两个人过河，再让第二快的去接最快的那个人。

我们得到了两个状态转移方程，只是我们只要取得他们之间的最小值就行了。所以说最终的状态转移方程是

f(i) = min( f(i-1) + 2*time[0] + time[i], f(i-2) + time[0] + time[i] + 2*time[1])

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/*  动态规划算法的线性模型
 * 【例题1】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，
 * 每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，
 * i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
 */

int size_time[10]{0};
int solution(vector<int>, int);

int solution(vector<int> person_time){
    return solution(person_time, person_time.size()-1);
}

// 备忘录类型的自上而下的动态规划，使用递归来实现
int solution(vector<int> person_time, int size){
    // 动态规划
    if (size_time[size] != 0){
        return size_time[size];
    }
    if (size == 0){
        size_time[0] = person_time[0];
        return size_time[0];
    }else if (size == 1){
        size_time[1] =  max(person_time[0],person_time[1]);
        return size_time[1];
    }else{
        // 递归的一个子问题，前几个怎么过，再加一个人怎么过？ 双数是怎么过？单数是怎么过？
        size_time[size] = min(solution(person_time, size-1)+person_time[0]+person_time[size],
                    solution(person_time, size-2) + person_time[0] + person_time[size] + 2*person_time[1]);
        return size_time[size];
    }
}

前面的那个动态规划的文章也说过了，我们完全可以将这里的递归转为递推。

int solution2(vector<int> person_time){
    int size = person_time.size()-1;
    size_time[0] = person_time[0];
    if (size == 0){
        return size_time[0];
    }
    size_time[1] = max(person_time[0], person_time[1]);
    if (size == 1){
        return size_time[1];
    }

    // 其实完全可以不使用数组，只使用三个变量就可以完事了，不过这个已经不是非常的重要了，问题不大
    // 自下而上的动态规划，使用递归的方式实现，比上面的算法更加的高效
    for (int i=2; i<=size; ++i){
        size_time[i] = min(size_time[i-1]+person_time[0]+person_time[i],
                        size_time[i-2]+person_time[0]+person_time[i]+2*person_time[1]);
    }

    return size_time[size];

}

int main(int argc, char const *argv[])
{
    vector<int> person_time = {5,1,2 ,10};
    sort(person_time.begin(), person_time.end()); // 一定要排序！
    cout<<solution2(person_time)<<endl;
    system("pause");
    return 0;
}

区间模型 回文串

/**
 * 动态规划算法的区间模型
 * 区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，
 * 然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。
 */

思路分析

【例题2】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。
分析：
典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，
在X两边各添加一个字符’a’后，aXa仍然是一个回文串，
我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，
那么对于A[i] == A[j]的情况，很明显有 d[i][j]= d[i+1][j-1]
（这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，
所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：

1. 在A[j]后面添加一个字符A[i]；

2. 在A[i]前面添加一个字符A[j]；

   根据两种决策列出状态转移方程为：
   d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; (每次状态转移，区间长度增加1)
   空间复杂度O(n^2)，时间复杂度O(n^2)， 下文会提到将空间复杂度降为O(n)的优化算法。

代码实现

#include <iostream>
#include <string>
#include <algorithm>
using std::string;
using std::cout;
using std::endl;
using std::min;

int memo[10][10]{0};

int func(string, int, int);
int func(string str){
    return func(str, 0, str.length()-1);
}

// 开始区间类型的动态规划 下面使用的时候备忘录类型的
int func(string str, int start, int end){
    if (memo[start][end] != 0){
        return memo[start][end];
    }
    if (start >= end){
        return 0;
    }
    if (str[start] == str[end]){
        return func(str, start+1, end-1);
    }else {
        memo[start][end] =  min(func(str, start+1, end), func(str, start, end-1))+1;
        return memo[start][end];
    }
}

int main(int argc, char const *argv[])
{
    string str = "srsher"; 
    cout<<func(str)<<endl;  
    system("pause");
    return 0;
}

0/1背包问题

0/1背包问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，
使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。

思路分析

这是我第三次看到这个问题。我们还是先开始来找子问题。比如有四个物品，我们将其按价格排个序。现在加入我们只是发第一个物品。得到金额。然后我们放两个物品，得到金额。问题就在放n个物品得到的金额和n-1个物品到底有没有关联呢？

可以第n个物品太重了，空间根本放不下，放n个物品的金额就是等于n-1个物品。

还有可能第n个物品可以放下去，还有剩余的空间，再用剩余的空间放那n-1个物品。

这两种方案并不能确定谁大谁小，所以说状态转移方程中，要比较他们的大小关系。

f(n, weight) = min{f(n-1, weight), v[n]+f(n-1 ,weight-w[n]))}

这里的weight其实指的是背包的容量还有多少。v数组指的是某一样物品的价格，w指的是某一样物品的重量

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using std::cout;
using std::endl;
using std::vector;
using std::max;

int memo[10][10]{0};

int func(vector<int> weight, vector<int> value, int i, int size){
    if (i == 0){
        if (weight[0] > size){
            return 0;
        }else {
            return value[0];
        }
    }
    if (memo[i][size] != 0){
        return memo[i][size];
    }
    if (weight[i] > size){
        return func(weight, value, i-1, size);
    }
    // 放入第i件物品，再使用剩下的空间放i-1件物品， 这样做到底有没有不放入第i件，只是使用前面的i件好？
    // 但是有个问题是，这个我们可能不知道到底把什么放入了背包？？？这个问题很大我感觉。。。
    // 不过，似乎用一个数组来表示是否被放入的状态可能可以解决
    memo[i][size] = max(func(weight, value, i-1, size), func(weight, value, i-1, size-weight[i])+value[i]);
    return memo[i][size];
}

int func(vector<int> weight, vector<int> value, int size){
    return func(weight, value, weight.size()-1, size);
}

int main(int argc, char const *argv[])
{
    vector<int> weight = {1,3,5,7,9};
    vector<int> value = {1,3,5,7,10};

    cout << func(weight, value, 100) <<endl;

    system("pause");
    return 0;
}

总结

上面的几道题目就是动态规划问题的经典问题。从这里我们基本就可以看出动态规划的问题到底该怎么解决。第一寻找子问题到底是什么？然后寻找状态转移方程，注意这个状态转移方程的多样性。其实之前的那个动态规划基本介绍中讲的蛮详细的，不过也蛮啰嗦的。不管了，动态规划就此了结吧，拜拜了您嘞！