动态规划算法与典型例题

$m[i][j]=\left\{\begin{matrix} 0 & ,j=i \\ r[i][j] &,j=i+1 \\ min \begin{Bmatrix} m[i][k]+m[k][j], r[i][j] \end{Bmatrix}& ,j > i+1 , i < k < j \end{matrix}\right.$

伪代码：

void rent()
{
    int i, j, k, d;
    for(d = 3, d <= n; ++d)//将问题分为小规模d。d=0时，租金为0；d=1时，租金为单站租金
    {
        for(i = 1; i <= n-d+1; ++i)//起点
        {
            j = i+d-1;//终点
            for(k = i+1; k < i+d-1; ++k)//换乘站，求解每一小规模子问题的解
            {
                int temp = m[i][k] + m[k][j];
                if(temp < m[i][j]) m[i][j] = temp;
            }
        }
    }
}

总体的求解过程为沿着主对角线一层一层向上，直到右上角填充完毕，则右上角值为所求解。

时间复杂度O(n^3)，空间复杂度O(n^2)。如果在原数组上更新计算值，则空间复杂度可以优化到O(1)。

五、典型例题2——0-1背包问题

问题描述：动态规划针对不可切割物品，可切割物品可以使用贪心算法。

约束条件：

$\left\{\begin{matrix} \sum w_i*x_i \leqslant W&,1 \leqslant i \leqslant n \\ x_i\in \begin{Bmatrix} 0,1 \end{Bmatrix}& ,1 \leqslant i \leqslant n \end{matrix}\right.$

目标函数：

$max\sum v_i*x_i, 1 \leqslant i \leqslant n$

c[i][j]表示前i件物品放入容量为j的购物车可以获得的最大价值。

递归式：

$c[i][j]=\left\{\begin{matrix} c[i-1][j] &, j<w_i \\ max\begin{Bmatrix} c[i-1][j], c[i-1][j-w[i]]+v[i] \end{Bmatrix}& ,j\geqslant w_i \end{matrix}\right.$

for(int i = 1; i <= n; ++i)
{
    for(int j = 1; j <= w; ++j)
    {
        if(j < w[i])//i物品重量大于购物车，则不放入
        {
            c[i][j] = c[i-1][j];
        }else{//比较i物品放入后能否让购物车价值最大
            c[i][j] = max(c[i-1][j], c[i-1][j-w[i]]+v[i]);
        }
    }
}

总体求解过程一层一层求解，右下角为所求解。

时间复杂度O(n*W)，空间复杂度O(n*W)。

六、典型例题3——跳台阶问题

问题描述：有 N 阶楼梯，每次可上一阶或两阶，求有多少种上楼梯的方法。

容易证明该递推式是斐波拉切数列，

$f(n) = n, n < 3$

$f(n)=f(n-1)+f(n-2), n\geqslant 3$

代码：

int jump(int n)
{
    if(n < 3) return n;
    int i = 1, j = 2, res = 0;
    for(int k = 0; k < n-2; ++k)
    {
        res = i + j;
        i = j;
        j = res;
    }
    return res;
}

时间复杂度O(n)，空间复杂度O(1)。

七、典型例题4——强盗抢劫问题

问题描述：强盗抢劫一排房间，每个房间都有钱，不能抢劫两个相邻的房间，要求抢的钱最多。

一维数组dp[i]是当抢到第i个数时，能抢到最大值，从局部最大值推到最终结果最大。

递归式：

$DP[i] = max(DP[i-2] + nums [ i ], DP[i-1])$

代码：

int robber(vector<int> &nums)
{
    int size = nums.size();
    if(size == 0) return 0;
    if(size == 1) return nums[0];

    vector<int> dp(size, 0);
    dp[0] = nums[0];
    dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
    
    for(int i = 2; i < size; ++i)
    {
        dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[size-1];
}

时间复杂度O(n)，空间复杂度O(n)。

总结

动态规划最大的优势在可以利用已知得出未知，求解过程中最重要且最困难的是要找出状态转移方程（递推式），同时还需要注意边界条件的设置。上述的经典问题解题思路具有较大参考价值。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

LeetCode

c