【转】动态规划DP

【数据结构与算法】 DP 动态规划介绍

原创 2017年02月13日 00:42:51

最近在看算法导论。

DP全称是dynamic programming，这里programming不是编程，是一个表格保存之前的结果。

DP 是一种编程思想，主要用于解决最优解类型的问题。

其思路是为了求解当前的问题的最优解，使用子问题的最优解，然后综合处理，最终得到原问题的最优解。

但是也不是说任何最优解问题都可以DP，使用dp的问题一般满足下面的两个特征：

（1）最优子结构，就是指问题可以通过子问题最优解得到；体现为找出所有的子问题最优解，然后取其中的最优；

（2）重叠子问题，就是子问题是会重复的。而不是一直产生新的子问题（比如分治类型的问题）。

一般而言，满足上述两个条件的最优解问题都可以会使用DP来解决。

DP在算法上的形式是什么？

有两种，一种是自顶向下，就是直接从原问题入手，不断利用子问题来求解，这种写法是一个递归地形式，但是需要加入备忘录，就是说利用一个数组存已经算出的子问题的结果，下次遇到直接返回。这个思路叫做memoization，备忘录。是一种空间换时间的做法，因为某些子问题会被调用到很多次，如果使用memo，那么时间上会很高效。比如求斐波那契数列，几乎每一个求解都会用到f(2)这样的子问题，如果事先存好，那么时间复杂度会下降很多。还有一点，memo不是为dp而生的，它也是一种思想或者技巧，在递归或者dfs中可以使用，如果要求时间复杂度可以考虑使用memo。

第二种是自底向上，这种不需要递归，就是不断地计算出小问题的解，然后后面的问题就可以利用小问题的解得到。

下面是算法导论中的一个简单的例子，给出一个长度为n的钢管，然后给出切割为不同长度以后的价格，问如何切割获利最大。

/**

 * @author miracle

 *切割钢条问题：

 *长度：1  2   3   4   5   6   7   8   9   10

 *价格：1  5   8   9   10  17  17  20  24  30

 *问长度为n的钢条的最多卖多少钱

 */

public class Solution {  

    int[] prices = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    int[] dp = new int[prices.length];

    public int solve(int[] prices, int n){

        if(n == 0) return 0;

        int max = Integer.MIN_VALUE;

        for(int i = 1; i <= n; i++){

            max = Math.max(max, prices[i] + solve(prices, n - i));

        }

        return max;

    }  

    public int solveWithMemoUpToBottom(int[] prices, int n){

        if(n == 0 || dp[n] > 0) return dp[n];

        int max = Integer.MIN_VALUE;

        for(int i = 1; i <= n; i++){

            max = Math.max(max, prices[i] + solve(prices, n - i));

        }

        dp[n] = max;

        return max;

    }  

    public int solveBottomToUp(int[] prices, int n){

        int[] dp = new int[prices.length];

        for(int i = 1; i <= n; i++){

            int max = Integer.MIN_VALUE;

            for(int j = 1; j <= i; j++){

                max = Math.max(max, prices[j] + prices[i - j]);

            }

            dp[i] = max;

        }

        return dp[n];

    }  

    public static void main(String args[]){

        Solution s = new Solution();

//      System.out.println(s.solve(s.prices, 1));

//      System.out.println(s.solve(s.prices, 2));

//      System.out.println(s.solve(s.prices, 3));

//      System.out.println(s.solve(s.prices, 4));

//      System.out.println(s.solve(s.prices, 5));

        System.out.println(s.solveBottomToUp(s.prices, 1));

        System.out.println(s.solveBottomToUp(s.prices, 2));

        System.out.println(s.solveBottomToUp(s.prices, 3));

        System.out.println(s.solveBottomToUp(s.prices, 4));

        System.out.println(s.solveBottomToUp(s.prices, 5));

    }

}

分别给出了不带memo，带memo的以及自底向上3中算法。

就实际情况来看，一般还是使用非递归的bottom to up类型。但是memo在递归中的使用也是一个小的技巧。

最后说下递归，dp，分治的区别。

递归只是一种编程的思想，只要自己调用自己，就算是递归。

分治，有三步，先分，再各自处理，最后整合。这里也涉及了子问题，这里的子问题是不重叠的，每一个只被处理一次，因此不需要memo。

dp，可以使用递归，而且dp的子问题是重复的。

dp说白了是子问题或者递归+memo，他其实是一种brute force，只不过记录了全部的结果，这就是为什么dp适用于解决最优解问题的原因（开头提到），其实它不一定非得解决最优解，只是它的思想使得它非常适合解决最优解问题。

巴特西

【转】动态规划DP

最新文章

热门文章