动态规划算法简介

动态规划基本介绍

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

适用情况

1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

求解的基本步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤，如下图所示：

初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

1. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

2. 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

3. 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

4. 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。实际应用中可以按以下几个简化的步骤进行设计：

1. 分析最优解的性质，并刻画其结构特征。

2. 递归的定义最优解。

3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值

4. 根据计算最优值时得到的信息，构造问题的最优解

算法实现

动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：

1. 问题的阶段

2. 每个阶段的状态

3. 从前一个阶段转化到后一个阶段之间的递推关系。

递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

上面的这些内容都是从百度百科中抄来的，虽然是百度百科讲的也不是很烂，我感觉除了不是很形象，其他讲的还是不错的。现在还是直接从leetcode动态规划算法的题目开始吧！

leetcode 动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

这个题目我之前就已经是做过了的，不过似乎是没有使用到动态规划的算法。

class Solution {
public:
    map<int, int> result;
    int climbStairs(int n) {
        if (n == 1 || n == 2) return n;
        if (result.find(n) != result.end()) return result[n];
        int res = climbStairs(n-1)+climbStairs(n-2);
        result[n] = res;
        return res;
    }
};

执行结果：通过 显示详情

执行用时 : 0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 : 8.7 MB, 在所有 C++ 提交中击败了10.62%的用户

由此可见，程序运行的速度是飞快的，但是因为使用了map进行记忆，程序消耗了太大的内存，所以说算法值得优化。这是一个典型的动态规划型的题目，和斐波那契数列有点儿相似，那么如何使用动态规划算法呢？

其实我上面用的map已经是一种动态规划算法了，就是记住原来算过的结果，极大的提高了效率，不过int， int类型的map如果是使用数组的话，还是更好一些。

class Solution {
    public static int memo[];
    public int climbStairs(int n) {
        memo = new int[n+1];
        return climbStairs(n, memo);
    }

    public static int climbStairs(int n, int memo[]){
        if (memo[n] != 0){
            return memo[n];
        }

        if (n == 1 || n == 2){
            memo[n] = n;
        } else {
            memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo);
        }

        return memo[n];
    }
}

执行结果：通过 显示详情

执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗 :33 MB, 在所有 Java 提交中击败了73.01%的用户

内存消耗反而变大了，，这个是语言的原因，你懂得~

改成C++代码

int climbStairs(int n){
    int* memo = new int[n+1]{0};
    return climbStairs(n, memo);
}

int climbStairs(int n, int* memo){
    if (memo[n] != 0){
        return memo[n];
    }
    if (n == 1 || n == 2){
        memo[n] = n;
    } else {
        memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo);
    }

    return memo[n];
}

执行结果：通过 显示详情

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.6 MB, 在所有 C++ 提交中击败了19.38%的用户

内存的消耗还是特别多，这。。。只能求助于题解了。可以不使用递归的方式，不过说实话，时间复杂度都是一样的，空间复杂度感觉也没多少改善啊。。。

int climbStairs(int n){
    if (n <= 2) return n;
    int* memo = new int[n+1]{0};
    memo[1] = 1;
    memo[2] = 2;
    for (int i=3; i<=n; ++i){
        memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
}

执行结果：通过 显示详情

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.4 MB, 在所有 C++ 提交中击败了43.73%的用户

算了，不纠结这题了，这只是一个简单题罢了，请看下一题。

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int max_sum = nums[0];

        for (auto i : nums){
            if (sum > 0){
                sum += i;
            }else {
                sum = i;
            }
            max_sum = max(sum, max_sum);
        }
        return max_sum;
    }
};

执行结果：通过 显示详情

执行用时 :8 ms, 在所有 C++ 提交中击败了92.04%的用户

内存消耗 :9.2 MB, 在所有 C++ 提交中击败了80.50%的用户

代码说明：

​ 别看着这个代码好像很简单似的，但是其中动态规划的算法还是不好理解的。

1. sum max_sum的含义是什么？

   sum表示的当前选定的序列的和，max_sum值的是遇到的最大的序列的和。

2. sum >0 -> sum += i ?

   这其实很好理解，前面的sum是正的，而且最大值已经被记录过了，加上前面正的序列对i有促进的作用，所以说新的序列就是前面的正的那一块加上当前的i.

3. else sum = i?

   前面的序列是负的，加上i无论i正负也好都不会有前面的序列大，所以直接从i开始一条新的序列就好了。

   那万一i前面的那个值是正的，为什么不从i前面的那个正数开始呢？

   不可能的，i前面的那个值既然被加入了序列中就说明，i前面的前面的序列的和是正数，而i前面的序列和是一个负数，这就可以肯定i前面的数是一个负数。所以从i开始新的序列的最对的。

4. max_sum = max(sum, max_sum);

   每次我们生成新的序列的，和都要和之前获取到的最大的数列的和进行比较以确保我们保存的的确是最大的子序列的和。

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

我一开始是这样子写的(纯暴力破解法，时间用的差不多是一千多ms吧，能AC我也是佛了)

int maxProfit(vector<int>& prices) {
    int profit = 0;
    int size = prices.size();
    for (int i=0; i<size-1; ++i){
        for (int j=i+1; j<size; ++j){
            if (prices.at(j) - prices.at(i) > profit)
                profit = prices.at(j) - prices.at(i);
        }
    }
    return profit;
}

其实这个题目一眼看过去就知道是动态规划的算法，和前面的那个题目是类似的

int maxProfit(vector<int>& prices) {
    int size = prices.size();
    if (size <= 1) return 0;
    if (size == 2) return max(prices.at(1) - prices.at(0), 0);

    vector<int> buy(size, 0);
    vector<int> sell(size, 0);
    buy.at(0) = -prices.at(0);
    for (int i=1; i<size; ++i){
        buy[i] = max(buy.at(i-1), -prices.at(i));
        sell[i] = max(sell.at(i-1), buy.at(i-1) + prices.at(i));
    }

    return *max_element(sell.begin(), sell.end());
}

执行结果：通过 显示详情

执行用时 :20 ms, 在所有 C++ 提交中击败了25.61%的用户

内存消耗 :9.8 MB, 在所有 C++ 提交中击败了5.10%的用户

这个问题的解决方案是动态规划当中比较经典的填表的方法。之前的那个百度百科中也都已经介绍了这个公式。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

与之比较类似的还有背包问题，待会可以一并解决。

代码说明：

上面的代码主要就是两行比较重要：

buy[i] = max(buy.at(i-1), -prices.at(i));
sell[i] = max(sell.at(i-1), buy.at(i-1) + prices.at(i));

第一个就是我在第i天买，比不比我在昨天买上算，如果今天比昨天还要贵那么我今天肯定是不买的。

第二个就是我在第i天卖有没有我在第i-1天卖上算，如果昨天卖比较好那还不如昨天卖。

但是光凭以上两点能解决什么问题呢？

仔细看的话，你会发现，其实你每一天买的都是相对来说最优的。而每天卖的也是最好的。

我们可以这样想，如何只有三天的话，我们是不是就可以获得在第三天卖的最高的价格？

假如是 1 2 5 只有buy[1] = 1 sell[1] = 2

第三天的价格是5，那buy[2] = 1，肯定还是延续在只有两天时的买法

sell[2] = max(sell[1], -1 + 5) ，这个卖就是sell[1]肯定是只有i两天的时候最优的利润，buy[1]也是最优的买法，现在加入就在第三天的时候，我们在第三天卖一下，我们看一看这个利润有没有之前的高。然后存入数组。

加上第四天的话还是这样子考虑。就这样其实sell数组里面放的就是有第n天的最大利润，sell数组后面值肯定也都是一样的。

于是取得最大值就行了。

return *max_element(sell.begin(), sell.end());

注意：max_element返回的是迭代器，所以要加上*取值。

leetcode给出的官方题解是这样子的

public int maxProfit(int prices[]) {
    int minprice = Integer.MAX_VALUE;
    int maxprofit = 0;
    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < minprice)
            minprice = prices[i];
        else if (prices[i] - minprice > maxprofit)
            maxprofit = prices[i] - minprice;
    }
    return maxprofit;
}

使我们感兴趣的点是上图中的峰和谷。我们需要找到最小的谷之后的最大的峰。 我们可以维持两个变量——minprice 和 maxprofit，它们分别对应迄今为止所得到的最小的谷值和最大的利润（卖出价格与最低价格之间的最大差值）。

这两个算法的思路其实都是一样的，不过官方的题解更加的清晰明了。不过我上面的那个更像是一个动态规划算法，把一个问题拆分成他的子问题。要取得第七天的最大的利润，我们需要利用第六天的数据，这就是一步一步往后推的过程。

买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

额~这个好像有点儿复杂，不过如果想到转换的话，一步头就完事了。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if (size == 1 || size == 0){
            return 0;
        }
        int profit = 0;
        for (int i= 1; i<size; ++i){
            if (prices[i] > prices[i-1]){
                profit += prices[i] - prices[i-1];
            }
        }

        return profit;
    }
};

执行结果：通过 显示详情

执行用时 :8 ms, 在所有 C++ 提交中击败了89.37%的用户

内存消耗 :9.5 MB, 在所有 C++ 提交中击败了48.29%的用户

感觉这个和动态规划已经扯不上边了，算了叭说了，反正我也不会。。。。

转载两篇文章，这个动态规划有点儿难，我特喵现在也有点儿懵逼了，算了不研究了，下次研究透彻了再说吧。

文章阅读

教你彻底学会动态规划——入门篇

算法-动态规划 Dynamic Programming–从菜鸟到老鸟