动态规划--未完待续

动态规划(Dynamic programming)

动态规划，通过把原问题分解为相对简单的子问题的方式求解复杂的问题。适用于有重叠子问题(递归求解时，子问题会被反复计算)和最优子结构性质(问题的解最优，则子问题的解也是最优的)的问题，动态规划的效率还是相对较高的，因为他会存储相似子问题的解。动态规划需要我们掌握子问题的状态，得到状态转移方程，问题也就解决了,而状态和状态转移方程是动态规划的核心。

我们可以举个例子，斐波那契数列：
如上一篇文章：递归 所述，斐波那契数列求和可以使用递归来求:

//递归求斐波那契数列前n个数的和
int Fibonacci(int n){
    if (n <= 1)  
        return n;  
    else  
        return Fibonacci(n-1) + Fibonacci(n-2);  
}

但是递归的效率并不高，他需要不停的调用函数，并且会出现重复计算子问题的情况，比如求Fibonacci(5):

Fibonacci(5)

Fibonacci(4)+Fibonacci(3)

Fibonacci(3)+Fibonacci(2)+Fibonacci(2)+Fibonacci(1)

Fibonacci(2)+Fibonacci(1)+Fibonacci(1)+Fibonacci(0)+Fibonacci(1)+Fibonacci(0)+Fibonacci(1)
.....

由上面的计算过程我们可以看出，出现了重复计算Fibonacci(2), Fibonacci(1)的情况。所以递归并不是很好的解决方案，这个时候动态规划就该上场了。。

int a[n];
int Fibonacci(int n) {
    if(n <= 1) {
        a[n]=n;
        return n;
    }
    if(a not contain n) {
        a[n] = Fibonacci(n-1)+ Fibonacci(n-2);
    }
    return a[n];
}

其实，在这个问题上，我们只是多建立了一个数组a来存储子问题的结果，这样就减少了重复计算子问题的值的情况。

接下来可以分析一下 poj 1018 的问题，有不同的设备，每种设备有不同的型号，不同的型号有不同的带宽和价格。选择n种设备，每种设备一款，求以最小代价拿到最大的带宽。初看题目就觉得应该用动态规划来做，然后动态转移方程是什么？变量有两个，带宽和价格，我们可以用一个二维数组 dp[i][j] 来表示选择了前 i 个宽带其容量为 j 的最小费用。 转移方程就是: dp[i][j] = min（dp[i][j]，dp[i-1][k]+p） k是那些可选的第k个元素

而 poj 1050 求最大子矩阵，最大子矩阵是在二维的情况下分析，我们可以先简化到一维。

比如：给出一个序列，求出连续的一段，使其和最大。

a[n]表示这个序列，a[i]表示第i个元素，可以得到一个状态方程，dp[i]表示以a[i]结尾的最大子段和，dp[i] = max{a[i], dp[i-1] + a[i]}，如果dp[i-1]>0,dp[i]=dp[i-1]+a[i],如果dp<0,则dp[i]=a[i],这个很容易理解，类似的还有求最长的子序列，同样的思路可以得到dp(i) = max{1, dp(j)+1},其中j<i,A[j]<=A[i]。接下来扩展到二维，求最大子矩阵，其实就是把二维的压缩到一维就好了，然后求一个最大和。其实类似的还有poj2479,求2段连续的段总和最大。

其实有一个入门的动态规划问题，那就是 01背包问题。有n种物品装入体积为V的背包中，求如何装才能使背包的重量最大，每种物品有且仅有一件。

遇到此类问题，我们可以假设F(i)表示在装第i件物品的时候背包的最大重量

#include <iostream>

int n;
int V, C[100], W[100], F[100][100];

using namespace std;
//01背包问题,状态转移方程：F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
//其实在空间复杂度上也可以优化为O：F[v] = max(F[v], F[v-C[i]]+W[i]);
void bag() {
    for (int i = 1; i <= n; i ++) {
        for (int v  = V; v > 0; v --) {
            F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
            printf("---F[%d][%d]:%d C[i]:%d W[i]:%d--------\n", i, v, F[i][v], C[i], W[i]);
//            F[v] = max(F[v], F[v-C[i]]+W[i]);
//            printf("---F[%d]:%d C[i]:%d W[i]:%d--------\n", v, F[v], C[i], W[i]);
        }
        printf("\n\n");
    }
}

int main(){
    cin >> n;
    cin >> V;
    for (int i = 1; i <= n; i ++) {
        cin >> C[i];
        cin >> W[i];
    }
    memset(F, 0, sizeof(F));
    bag();
    printf("%d",F[n][V]);
//    printf("%d",F[V]);
    return 0;
}