动态规划笔记（二）

作者: Ice_spring | 来源:发表于2020-03-13 17:26 被阅读0次

动态规划笔记（二）
LeetCode—— 不同路径
2. 动态规划 Dynamic Programming
强化学习读书笔记 - 04 - 动态规划
《算法图解》note 9 动态规划
走楼梯——二维带权值走楼梯（四）
初识动态规划
走楼梯——二维有障碍走楼梯（五）
走楼梯——二维带权值带特殊条件加倒着走楼梯（六）
动态规划笔记

内容概要：

动态规划的状态及状态转移
0-1背包问题
背包问题的若干变种

状态及状态转移方程

上篇文章我们知道，可以用动态规划解决的问题往往都具有重叠子问题和最优子结构，我们每次解决其中的一个子问题，最终将子问题的答案并到一块，原问题也就得到解决。为了更加清晰地描述这种求解(决策)过程，在动态规划中定义状态及状态转移。所谓状态就是在算法里我们要保存的每一步的求解结果，而状态转移就是后续要求解的子问题与当前已有的1个或多个状态之间的关系，或称状态转移方程。比如在求 $Fibonacci$ 数列的第 $n$ 项时，每一项都是一个状态，每求一个项只需要之前的两个状态，状态转移方程：
$a_n=a_{n-1}+a_{n-2},n \geq 3$

下面来通过一个简单的例子看一看状态及状态转移方程的作用：
LeetCode198 House Robber问题链接

LeetCode198

对于这个问题，定义状态：

$f(k) = 从[k,n) 房屋中能偷取到的最大钱数，nums[i]= 第 i 个房屋的钱数$

则有：
$f (n)=0,f(n-1)=nums[n-1]$ 这可以看做是系统初始状态，不难理解 $f(n)$ 表示没有可偷的房间，故为0； $f(n-1)$ 表示只能偷最后一个房间，故为 $nums[i]$ ，这样接着写下去：
$f (n-2)=max(nums[n-2],f(n-1)), f(n-3)=max(nums[n-3]+f(n-1),f(n-2))...$

不难写出对应的状态转移方程：
$f(k) = max(nums[k] + f(k+2),f(k+1))$

于是很轻松地给出动态规划代码：

class Solution198_1 {//动态规划
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)return 0;
        vector<int> memo(n+1, -1);
        memo[n] = 0; //抢劫[index,n)
        memo[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            memo[i] = max(nums[i]+memo[i+2],memo[i+1]);
        }
        return memo[0];
    }
};

上述代码时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ (因为我们用memo将所有状态保存了下来。实际上如果看计算过程，会发现每个状态的求解只用到了前两个状态，故空间复杂度可以优化到 $O(1)$ )。

当然状态的定义也可以不同，这样一来得到的代码逻辑也会有区别，比如也可以定义
$f(k) = 从[0,k] 房屋中能偷取到的最大钱数，nums[i]= 第 i 个房屋的钱数$

此时 $f(1)=nums[1],f(2)=max(nums[1],nums[2])$ ，接着往下写不难得到状态转移方程：
$f(k) = max(nums[k] + f(k-2),f(k-1))$

对应的动态规划代码：

class Solution198_2 {//动态规划
public:
    int rob(vector<int>& nums) {
        int memo_pre = 0, memo_cur = 0;
        for (int i = 0; i < nums.size(); i++) {
            int temp = memo_cur;
            memo_cur = max(nums[i] + memo_pre, memo_cur);
            memo_pre = temp;
        }
        return memo_cur;
    }
};

该代码的时间复杂是 $O(n)$ ，空间复杂度是 $O(1)$ (因为只保留了会参与计算的两种状态。)

不管用哪种状态定义，我们看到，当状态和状态转移清晰时，代码的书写也会非常的流畅，所以有必要掌握寻找状态和状态转移方程的能力。下面再来看一个动态规划中的经典问题。

0-1背包问题

0-1背包问题描述：给定编号从0到n-1的一组物品，每种物品都有自己的重量w和价值v，现在有一个承重有限的背包，承重量为C，问：我们如何选择装入背包的物品，才能使得物品的总价值最高。
定义状态 $f(k,C)$ ：
$f(k,C)表示选择[0,k]区间的一些物品放入容量为C的背包，获得的最大价值，\\ w[k]表示第k个物品的重量，v[k]表示第k个物品的价值$ 于是得到状态转移方程： $f(k,C)=max(f(k-1,C),v[k]+f(k-1,C-w[k])$ 按照这个逻辑，首先给出问题的递归(记忆化搜索)代码：

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
class Knapsack01_2 {
    // 记忆化搜索
// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
// 空间复杂度: O(n * C)
public:
    vector<vector<int>>memo;
    //用[0,...,index] 的物品，填充容积为c的背包获得的最大价值
    int bestValue(const vector<int>& w, const vector<int> v, int index, int c) {
        if (index < 0 || c <= 0)return 0;//无法选物品或者没有容量
        if (memo[index][c] != -1)return memo[index][c];
        int res = bestValue(w, v, index - 1, c);//策略1，不选index号物品
        if (c >= w[index])//背包还能容纳编号为index的物品
            res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));//策略2
        memo[index][c] = res;
        return res;
    }
    int solve(const vector<int>& w, const vector<int>& v, int C) {
        int n = w.size() - 1;
        memo = vector<vector<int>>(n, vector<int>(C + 1, -1));
        return bestValue(w, v, n - 1, C);
    }
};
int main() {//测试
    int n, C;
    cout << "请输入物品数量n和背包的承重量C：" << endl;
    cin >> n >> C;
    int v, w;
    vector<int> vs, ws;
    cout << "请输入各个物品的重量和价值：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> w >> v;
        vs.push_back(v);
        ws.push_back(w);
    }
    cout << "最大价值为：" << Knapsack01_2().solve(ws, vs, C) << endl;
    return 0;
}

设背包承重量为5，各个物品重量和价值如下表，测试上述代码。

index	0	1	2	3
weight	1	2	3	4
value	9	10	12	8

测试结果如下：

0-1背包

可以检验，结果是正确的。
下面再给出动态规划的代码：

class Knapsack01_1 {
    // 动态规划O(n*C)O(n*C)
public: 
    int solve(const vector<int>& w, const vector<int>& v, int C) {
        assert(w.size() == v.size());
        int n = w.size();
        if (n == 0)return 0;
        vector<vector<int>>memo(n, vector<int>(C + 1, -1));
        for (int j = 0; j <= C; j++)
            memo[0][j] = (j >= w[0] ? v[0] : 0);//基础状态

        for (int i = 1; i < n; i++)
            for (int j = 0; j <= C; j++) {
                memo[i][j] = memo[i - 1][j];
                if (j >= w[i])
                    memo[i][j] = max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
            }
        return memo[n - 1][C];
    }
};

其中的状态量memo[i][j]表示[0:i]号物品放入承重量位j的背包的最大价值。
读者可自行测试其正确性。
0-1背包问题的空间复杂度优化
观察状态转移方程我们发现在求解一个新状态时，实际上只用到了两个状态，这样我们可以将空间复杂度优化到 $O(C)$ 。

class Knapsack01_3 {
public: 
    int solve3(const vector<int>& w, const vector<int>& v, int C) {
        assert(w.size() == v.size());
        int n = w.size();
        if (n == 0)return 0;
        vector<int>memo(C + 1, -1);
        for (int j = 0; j <= C; j++)
            memo[j] = (j >= w[0] ? v[0] : 0);//基础状态

        for (int i = 1; i < n; i++)
            for (int j = C; j >= w[i]; j--)
                memo[j] = max(memo[j], v[i] + memo[j - w[i]]);
        return memo[C];
    }
};

0-1背包问题的变种

完全背包问题和多重背包问题
完全背包问题是每种物品数量无限的背包问题，实际上由于背包容量有限，每种物品还是有上限的，这类问题可以转化为0-1背包问题。
多重背包问题是每种物品数量有限，同样可以转化为0-1背包问题。
多维费用背包问题
这类背包问题对背包的限制会增多，如从体积和容量两个维度约束背包。
物品互相排斥或依赖的背包问题
排斥：放入某些物品后就不能放入另一些物品了；
依赖：放入某些物品后必须放入另一些问题。
几个可转化为0-1背包问题的例子
LeetCode416 链接

LeetCode416

这个问题就是典型的0-1背包问题变种，相当于在 $n$ 个物品中选取一部分物品，填满容量为 $C$ 的背包(C在本题中为数组和的一半)，而且这个问题更加简单，因为不牵扯物品的价值，不过这里返回的是布尔值：
设 $f(n,C)$ 表示使用[0:n-1]的n个物品物品填满容量为 $C$ 的背包，于是对于 $\forall{k}$ ，有状态转移方程：
$f(k,C)=f(k-1,C)||f(k-1,C-w[i])$

它表示当考虑[0,k]区间的物品能否填满容量为C的背包时，首先看[0:k-1]是否能填满，否则看当前物品加入后是否能填满，也就是[0:k-1]是否能填满总容量C减去第k个物品的重量。
由状态转移方程，不难给出动态规划代码：

class Solution {//O(n*sum)
    //动态规划
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1)return false;
        int n = nums.size();
        int C = sum / 2;
        vector<bool>memo(C + 1, false);
        //看容量为i的情况下第一个物品是否能填满它
        for (int i = 0; i <= C; i++)
            memo[i] = (nums[0] == i);

        for (int k = 1; k < n; k++)
            for (int i = C; i >= nums[k]; i--)
                memo[i] = memo[i] || memo[i - nums[k]];
        return memo[C];
    }
};

LeetCode322 链接

LeetCode322

这个问题也是背包问题的一个简单变种，定义 $f(i)$ 为组成金额 $i$ 所需最少的硬币数量，则对应的状态转移方程应为：

$f(i)=(\min_{j=0 \ldots n-1}{f(i -w_j)} )+ 1$

其中 $w_j$ 代表的是第 $j$ 枚硬币的面值，上述状态转移方程的含义是，我们枚举的最后一枚硬币面额是 $w_j$ ，则需要从 $i-w_j$ 这个金额的状态 $f(i-w_j)$ 转移过来，再算上枚举的这枚硬币数量1的贡献，所以 $f(i)$ 为前面能转移过来的状态的最小值加上枚举的硬币数量1。动态规划代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //最坏全是1元硬币，不可能超过amount+1个;
        vector<int> memo(amount + 1, amount + 1);
        memo[0] = 0;//金额为0不能由硬币组成
        for (int i = 1; i <= amount; ++i) 
            for (int j = 0; j < coins.size(); ++j) 
                if (coins[j] <= i) 
                    memo[i] = min(memo[i], memo[i - coins[j]] + 1);
        return memo[amount] > amount ? -1 : memo[amount];
    }
};

动态规划笔记（二）
内容概要：动态规划的状态及状态转移 0-1背包问题背包问题的若干变种状态及状态转移方程上篇文章我们知道，可...
LeetCode—— 不同路径
题目描述一、CPP 1. 动态规划法：解题思路:详解异步动态规划笔记——类型二：计数型。时间复杂度:O(n2...
2. 动态规划 Dynamic Programming
动态规划笔记 dynammic programming notes Table of contents Defin...
强化学习读书笔记 - 04 - 动态规划
请看原文强化学习读书笔记 - 04 - 动态规划
《算法图解》note 9 动态规划
这是《算法图解》的第九篇读书笔记，主要内容是动态规划的简介。 1.动态规划定义动态规划指的是在约束条件下，将问题...
走楼梯——二维带权值走楼梯（四）
LeetCode_64_MinimumPathSum 题目分析：解法一：循环-动态规划解法二：循环-动态规划-...
初识动态规划
0-1 背包问题备忘录动态规划-二维数组动态规划-一维数组 0-1 背包问题升级版回溯算法动态规划-二维...
走楼梯——二维有障碍走楼梯（五）
LeetCode_63_UniquePathsII 题目分析：解法一：循环-动态规划解法二：循环-动态规划-递...
走楼梯——二维带权值带特殊条件加倒着走楼梯（六）
LeetCode_174_DungeonGame 题目分析：解法一：循环-动态规划解法二：循环-动态规划-内存...
动态规划笔记
动态规划篇动态规划(Dynamic Programming,DP),是一种优化问题的思路,其核心思想是:把一个问...