• 欢迎访问最初的梦想
  • Github https://github.com/anthonyzhai

动态规划

编程 AnthonyZhai 2个月前 (08-15) 54次浏览 已收录 0个评论

1 例题引出动态规划

给定数组arr,arr中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim代表要找的钱数,求换钱有多少种方法。

1.1 记忆搜索方法与动态规划方法的联系

1)是某种形态的动态规划
2)不关心到达某一递归过程的路径,只是单纯地对计算过的递归过程进行记录,避免重复的递归过程;
3)动态规划则是规定好每一个递归过程的计算顺序,依次进行计算,后面的计算过程严格依赖前面的计算过程;
4)两者都是空间换时间的方法,都有枚举的过程,区别就在于动态规划规定计算顺序,而记忆搜索不用规定。

1.2 动态规划

1)生成行数为N,列数为aim+1的矩阵dp;
2)dp[i][j]的含义是在使用arr[o…i]货币的情况下,组成钱数j有多少种方法;
3)第1行代表只使用arr[0]这一种货币所能组成的aim钱数;第1列代表组成aim为0的方法数,显然不使用任何货币;
动态规划
4)如果用k张arr[i]货币,剩下的钱用arr[0…i-1]货币组成时,方法数为dp[i-1][j-k*arr[i]]。其中,k=0,完全不用arr[i]货币;k=1,只用1张arr[i]货币;k代表使用k张arr[i]货币;
5)先从左到右计算dp中每行的值;再从上到下计算下一行的值;
6)每个位置都需要枚举,时间复杂度为$O(aim)$,dp中一共有$N * aim$个位置,所以总体时间复杂度为$O(N * aim^2)$。

1.3 什么是动态规划方法

1)申请的空间来记录每一个暴力搜索的计算结果,下次要用结果的时候直接使用,而不在进行重复的递归过程。
2)规定每一种递归状态的计算顺序,一次进行计算。
优化dp[i][j]的求法,dp[i][j]等于如下值的累加:
$$
dp[i-1][j]\\
dp[i-1][j-1arr[i]]\\
dp[i-1][j-2
arr[i]]\\
dp[i-1][j-3*arr[i]]\\
$$
则$dp[i][j]=dp[i][j-arr[i]]+dp[i-1][j]$,简化后的时间复杂度为$O(N * aim)$。

1.4 实现动态规划方法的步骤:

1)实现暴力递归方法;
2)在暴力搜索中寻找可以代表递归过程的参数;
3)实现记忆化搜索方法;
4)通过分析记忆化搜索的依赖路径,实现动态规划
5)是否可以优化。

1.5 关键点

1)最优化原理;
2)无后效性;
3)子问题的重叠性。

2 上台阶问题

有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法?

$f(i)=f(i-1)+f(i-2)$,走到i层台阶的方法数量=走到i-1层台阶的方法数量+走到i-2层台阶的方法数量。

2.1 暴力搜索方法

int climbStairs(int n){
    if(n<1) return 0;
    if(n==1 || n==2)    return n;
    return climbStairs(n-1)+climbStairs(n-2);
}

2.2 动态规划

int climbStairs(int n) {
    vector<int> stairsNum(n+1);
    for(size_t i=1;i<=n;++i){
        if(i==1 || i==2)
            stairsNum[i] = i;
        else
            stairsNum[i]= stairsNum[i-1] + stairsNum[i-2];
        }
    return stairsNum[n];
}

3 矩阵路径和最小问题

给定一个矩阵m,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有数字累加起来就是路径和,返回所有的路径中最小的路径和?

$$
当i=0 且 j=0时,dp[0][0]=matrix[0][0]\\
当i\geq1 且 j\geq1时,dp[i][j]=matrix[i][j] + min(dp[i][j-1], dp[i-1][j])\\
当i=0 且 j\geq1时,dp[0][j]=matrix[0][j]+dp[0][j-1]\\
当j=0 且 i\geq1时,dp[i][0]=matrix[i][0]+dp[i-1][0]
$$
动态规划

int minPathSum(vector<vector<int>>& grid) {
    size_t m = grid.size();
    size_t n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, grid[0][0]));
    for(size_t i=1;i<m;++i)
        dp[i][0] = grid[i][0] + dp[i-1][0];
    for(size_t j=1;j<n;++j)
        dp[0][j] = grid[0][j] + dp[0][j-1];
    for(size_t i=1;i<m;++i)
        for(size_t j=1;j<n;++j)
            dp[i][j]=grid[i][j] + min(dp[i][j-1], dp[i-1][j]);
    return dp[m-1][n-1];
}

4 最长递增子序列问题

给定数组arr,返回arr的最长递增子序列(可以不连续)长度?

dp[i]表示在必须以arr[i]为结尾的情况下,arr[0…i]中最大递增子序列长度。
$dp[i]=max(dp[j]+1),0 \leq j < i,arr[j] < arr[i]$

int lengthOfLIS(vector<int>& nums) {
    size_t len=nums.size();
    vector<int> dp(len, 1);
    for(size_t i=1;i<len;++i){
        int max = 0;
        for(size_t j=0;j<i;++j){
            if(nums[i] > nums[j] && max < dp[j])
                max = dp[j];
        }
        dp[i] = max + 1;      
    }
    int result=0;
    for(size_t i=0;i<len;++i)
        if(result < dp[i])
            result=dp[i];
    return result;
    }

5 最长公共子序列问题

给定两个字符串str1和str2,返回两个字符串的最长公共子序列。

假设str1长度为M,str2的长度为N,生成大小为M*N的矩阵dp。dp[i][j]的含义是str1[0…i]与str2[0…j]的最长公共子序列的长度。

1)如果str[i]==str2[0],则令dp[i][0]=1,dp[i+1…M][0]=1。
2)dp[0][j]与1)中同理,一旦dp[0][j]=1,则dp[0][j+1…N]=1。
3)dp[i][j]有三种取值情况:
+ dp[i-1][j]
+ dp[i][j-1]
+ dp[i-1][j-1]+1
选择其中最大值。

int findLength(vector<int>& A, vector<int>& B) {
    size_t M = A.size();
    size_t N = B.size();
    vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
    for(size_t i=1;i<=M;++i){
        for(size_t j=1;j<=N;++j){
            if(A[i-1] == B[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    } 
    return dp[M][N];
    }

6 背包问题

6.1 01背包

一个背包有一定的承重W,有N件物品,每件都有自己的价值,记录在数组v中,也都有自己的重量,记录在数组w中,没见物品只能选择装入背包还是不装入背包,要求在不超过背包承重的前提下,选出物品的总价值最大。

假设物品编号从1到n,一件一件物品考虑是否加入背包。假设dp[x][y]表示前x件物品,不超过重量y的时候的最大价值。枚举以下第x件物品的情况:
+ 如果选择第x件物品,则x-1件物品的重量不能超过y-w[x];
+ 如果不选择第x件物品,则x-1件物品的重量不超过y;

所以,dp[x][y]=max{dp[x-1][y], dp[x-1][y-w[x]]+v[x]};


6.2

7

给定两个字符串str1和str2,再给定三个整数ic,dc和rc,分别代表插入、删除和替换一个字符的代价。返回将str1编辑成str2的最小代价。

假设str1的长度为M,str2的长度为N,首先生成大小为(M+1)*(N+1)的矩阵dp,dp[i][j]的值代表str[0…i-1]编辑成str[0…j-1]的最小代价。
+ dp[0][0]=0;
+ dp[i][0]=dc * i
+ dp[0][j]=ic * j
+ dp[i][j]的值有以下四种情况:
+ (多)删除str1[i-1],dp[i][j]=dc + dp[i-1][j]
+ (少)插入str2[j-1],dp[i][j]=ic + dp[i][j-1]
+ (不等)替换str1[i-1]为str2[j-1],dp[i][j]=dp[i-1][j-1]+rc
+ (相等)dp[i][j]=dp[i-1][j-1]
+以上4中可能值,选最小值作为dp[i][j]的值。
+ 最终的值为dp矩阵右下角的值。


棍切割

长度$i$ 1 2 3 4 5 6 7 8 9 10
价格$P_i$ 1 5 8 9 10 17 17 20 24 30

分拆函数

  1. $P(n)$分拆函数,$n$;
  2. Hardy和Ramanujan得到$P(n) \approx \frac{1}{4n\sqrt{3}} e^{\pi\sqrt{\frac{2n}{3}}}$;
  3. 自顶向下递归
int recursive_cr(const vector<int>& p, size_t n)
{
    int r = p[0];
    for(size_t i = 1; i<=n; ++i)
        if(p[i]+recursive_cr(p, n-i) > r)
            r = p[i]+recursive_cr(p, n-i);
    return p;
}

最优子结构

int look_up(vector<vector<int>>& m, const vector<int>& p, size_t i, size_t j)
{
    //i<=j
    if(m[i][j] != -1)
        return m[i][j];
    if(i == j)
        return 0;
    else
    {
        //i<j
        m[i][j] = look_up(m, p, i, i)+look_up(m, p, i+1, j)+p[i-1]* p[i]*p[j];
        for(size_t k = i+1; k<j; ++k)
        {
            int cost = look_up(m, p, i, k)+look_up(m, p, k+1, j)+p[i-1]*p[k]*p[j];
            if(cost < m[i][j])
            m[i][j] = cost;
        }
    }
    return m[i][j];
}

int memoized_matrix_chain(const vector<int>& p)
{
    if(p.size() <= 1)
        return 0;
    size_t n = p.size()-1;
    vector<vector<int>> m(n+1);
    for(size_t i=1; i<m.size(); ++i)
    {
        m[i].resize(n+1, -1);
        return look_up(m, p, 1, n);
    }
}

最初的梦想 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:动态规划
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址