动态规划算法详解

布满荆棘的人生 2022-09-23 09:29 93阅读 0赞

# 动态规划的介绍 #

动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。

# 基本思想及其与分治法的区别： #

将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解（这部分与分治法相似）。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。通常可以用一个表来记录所有已解的子问题的答案。

## 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思路。 ##

# 动态规划算法的4个步骤： #

## 1.描述最优解的结构 ##

## 2.递归定义最优解的值 ##

## 3.按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础。 ##

## 4.由计算出的结果构造一个最优解。 //此步如果只要求计算最优解的值时，可省略。 ##

# 采用动态规划求解的问题需要具有两个特性： #

## 最优子结构（Optimal Substructure）： ##

问题的一个最优解中所包含的子问题的解也是最优的。总问题包含很多个子问题，而这些子问题的解也是最优的。

## 重叠子问题（Overlapping Subproblems）： ##

用递归算法对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

# 典型例题： #

## 有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法? ##

## 分析 ##

：很显然，这道题的对应的数学表达式是

## F(n)=F(n-1) + F(n-2); ##

其中F(1)=1, F(2)=2。很自然的状况是，采用递归函数来求解：

int  solution(int n){  
        if(n>0 && n<2) return n;  
        return solution(n-1) + solution(n-2);  
    }

如果我们计算F(10), 先需要计算F(9) F(8); 但是我们计算F(9)的时候，又需要计算F(8)，很明显，F(8)被计算了多次，存在重复计算；同理F(3)被重复计算的次数就更多了。算法分析与设计的核心在于 根据题目特点，减少重复计算。 在不改变算法结构的情况下，我们可以做如下改进：

int dp[11];  
    int  solution(int n){  
        if(n>0 && n<2) return n;  
        if(dp[n]!=0) return dp[n];  
        dp[n] = solution(n-1) + solution(n-2);  
        return  dp[n];  
    }

## 这是一种递归形似的写法，进一步，我们可以将递归去掉： ##

int  solution(int n){  
        int dp[n+1];  
        dp[1]=1;dp[2]=2;  
        for (i = 3; i <= n; ++i){  
            dp[n] = dp[n-1] + dp[n-2];  
        }  
        return  dp[n];  
    }

# 动态规划的五个典型算法（见我其他的博客） #

## 1.最大连续子序列之和 ##

[最大连续子序列之和的博客链接][Link 1]

## 2.数塔问题（二叉树从上往下遍历最大和问题） ##

## 3.01背包问题 ##

## 4.最长递增子序列(LIS) ##

## 5.最长公共子序列(LCS) ##

[最长公共子序列(LCS)的博客链接][LCS]

参考：  
[http://blog.csdn.net/zmazon/article/details/8247015][http_blog.csdn.net_zmazon_article_details_8247015]  
[http://blog.csdn.net/lisonglisonglisong/article/details/41548557][http_blog.csdn.net_lisonglisonglisong_article_details_41548557]  
[http://blog.csdn.net/v\_JULY\_v/article/details/6110269][http_blog.csdn.net_v_JULY_v_article_details_6110269]  
[http://blog.csdn.net/trochiluses/article/details/37966729][http_blog.csdn.net_trochiluses_article_details_37966729]

[Link 1]: http://blog.csdn.net/lpjishu/article/details/51935625
[LCS]: http://blog.csdn.net/lpjishu/article/details/51935023
[http_blog.csdn.net_zmazon_article_details_8247015]: http://blog.csdn.net/zmazon/article/details/8247015
[http_blog.csdn.net_lisonglisonglisong_article_details_41548557]: http://blog.csdn.net/lisonglisonglisong/article/details/41548557
[http_blog.csdn.net_v_JULY_v_article_details_6110269]: http://blog.csdn.net/v_JULY_v/article/details/6110269
[http_blog.csdn.net_trochiluses_article_details_37966729]: http://blog.csdn.net/trochiluses/article/details/37966729