about Dynamic Programming 「DP/动态规划」

子问题最优则原始问题最优——贪心算法或者动态规划算法。
子问题最优则原始问题最优，且子问题互相独立——分治算法。
子问题最优不能推导出原始问题最优——暴力搜索等。

如果子问题最优则原问题最优，贪心算法。
如果子问题需要全部求解才能求解原问题，子问题互相独立，分治算法。
如果子问题最优不能保证原问题最优，但是子问题之间不会循环（所谓循环，是指从问题 A 拆解出子问题 B，然后子问题 B 又能拆解出子问题 A），考虑动态规划算法。
更加复杂的情况，我们总是可以考虑暴力搜索解决。

分治「Divide and Conquer Algorithm 」

值的注意的是 : 贪心算法在解决01背包问题的时候错误很明显 所以你最好能够证明这个题可以使用贪心算法.

分治和动态规划的思想区别本质在于: 分治的子问题毫无关联, 而动态规划则是子问题的嵌套「所以需要状态转移方程」

动态规划:

在不问最优解 只问最优值的时候 可以尝试动态规划

1. 递归 直接基于状态转移方程来实现

2. 自顶向下(记忆化) 相当于是查表 「重叠子结构」

3. 自底向上(迭代)

   1. 有了状态转移方程，我们就知道如何从最小的问题规模入手，然后不断地增加问题规模，直到所要求的问题规模为止。在这个过程中，我们同样地可以记忆每个问题规模的解来避免重复的计算。这种方法就是自底向上的方法，由于避免了递归，这是一种更好的办法。

      但是迭代法需要有一个明确的迭代方向，例如线性，区间，树形，状态压缩等比较主流的动态规划问题中，迭代方向都有相应的模式。参考后面的例题。但是有一些问题迭代法方向是不确定的，这时可以退而求其次用记忆化来做，参考后面的例题。

动态规划存在无后效性的原则 「状态必须是确定的」

e.g. 丢n枚硬币, 我们求其中k个朝上的概率是多少

设立矩阵 p[i] [j] 其中i代表丢下第i枚硬币, j代表 其中在这次丢硬币之前有 j 枚朝上

显然 我们有这样的状态转移方程: p[i] [j] = p[i-1] [j-1] * 0.5 + p[i-1] [j] * 0.5

现在我们改变问题 当连续两次丢下硬币都朝着一面的时候, 下一次丢硬币一定会是另一面. 因为我们的状态里没有包含前两次的结果, 所以显然刚才的状态方程是错误的, 如果想要使用动态规划, 这里应该添加两个维度, 来存储上一次 和上上次的结果.

动态规划的最优子结构 「在设计状态的时候, 我们应当保证最优的状态只从之前的最优状态来, 而不是从之前的非最优状态来」

比如01背包问题, 如果我们加入一个条件, 某两件物品一起拿能够产生额外价值, 那么就不适用动态规划了.

重叠子结构

比如在解斐波那契的时候 , 我们加入一个dp[n], 存储每一次的答案, 不需要重复计算,

动态规划例题:

1. 编辑距离 II 在编辑距离的基础上, 不允许插入操作, 这意味着在A删除和在B删除是有区别的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    // 在A中删除一个字符 或者替换
    int edit_distance(string s, string t) {
        int n = s.length(), m = t.length();
        if (!(n * m)) return m + n;
        
        // 请务必注意dp边界的初始化 请一定要注意
        int dp[n+1][m+1];
        for (int i = 0; i <= n; ++i) dp[i][0] = i;
        for (int i = 0; i <= m; ++i) dp[0][i] = i;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1];
                // 问题就在于 s的子串长度一定要超过 t 的子串长度. 否则不应删减掉
                else dp[i][j] = i > j ? min(dp[i-1][j-1], dp[i-1][j])+1 : dp[i-1][j-1] + 1; 
            }
        }
        return dp[n][m];   
    }
};

2. 打家劫舍I 「给定一个序列, 我们不能连着偷相邻的两家, 求我们能获取的最大利润是多少」

示例1

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例2

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路: 四种DP的方式 「无非就是从增加维度控制后效性 $\rightarrow$ 不增加维度的dp优化」

1. 2维DP dp[i] [0] 代表不偷第 i 间, 前i间房能获取的最大利润 dp[i] [1]则是偷第i间. 显然 dp[i] [0] = max(dp[i-1] [1], dp[i-1] [0]), 而dp[i] [1] = dp[i-1] [0] + nums[i] (因为偷这一间意味着上一间肯定不能偷啦 )

2. 1维DP 法1

   • 这种思路是错误的 「我们通过dp[i-1」和dp[i-2]是否相同来判断是否可以偷第[i]间, 但是问题就在于, 每两间房必会偷一间, 但显然, 这种方式无法每次都找到最优解.

3. 1维DP 法2

   • dp[i] 确实有两种情况 1. 不偷 dp[i] = dp[i-1] (显然, 上一个房间也不一定非要偷) 2. 偷 dp[i] = dp[i-2] + nums[i];

   • 所以dp[i] = max(dp[i-1], dp[i-2]+nums[i])

4. 0维DP 直接上代码 两个变量相互继承, 有点类似之前做过的最长湍流子数组? 是吗

   1 2 3 4 5 6 7 8 9 10 11 12

   int rob(vector<int>& nums) { int n = nums.size(); if (!n) return 0; if (n == 1) return nums[0]; int rob = nums[0], nrob = nums[1]; for (int i = 2; i < n; ++i) { int temp = rob; rob = max (rob, nrob); nrob = temp + nums[i]; } return max(rob, nrob); }

   打家截舍II 现在第一间房屋和最后一间房屋连起来 偷第一间就不可以偷最后一间

   改变区间就可以了. 如果偷第一家 就把最后一家从区间中去掉. (根据一维dp法2来做)

3. 预测赢家 「给定一组牌(数组), 我们只能从最后或者最前面拿牌, 玩家1先手, 我们 希望能在给定序列的情况下, 提前知道玩家1是否可以赢(假设两名玩家都绝顶聪明)」

此题出现了 dp[i]由 dp[i+1] 和 dp[i+2] 推导而来的情况, 我们需要通过一个矩阵来解决这个问题. 麻烦画一下 现在我懒得画了 其实比较容易.

示例1

输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。

示例2

输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    // dp[i][j] 表示玩家1 在牌i到牌j可以拿到的最大分数; 最终的结果是 dp[i][nums.size()-1]
    // dp[i][j] = max (left, right);  left -> 拿左边的, right -> 拿右边的
    // left = min(dp[i+1][j-1], dp[i+2][j]) + nums[i] 站在玩家2的角度上思考,他必然选择最优解, 这意味着玩家1之后将拿到的只能是最小值. 
    // right = min(dp[i+1][j-1], dp[i][j-2]) + nums[j];
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size(), sum = accumulate(nums.begin(), nums.end(), 0);
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; ++i) dp[i][i] = nums[i];
        for (int i = 0; i < n - 1; ++i) dp[i][i+1] = max(nums[i], nums[i+1]);
        for (int l = 3; l <= n; ++l) {
            //l作为长度, 最开始至少有3三张, 我们从前3张卡开始,不断的向外扩散
            for (int i = 0; i + l - 1 < n; ++i) {
                int j = i + l - 1;
                int left = min(dp[i+1][j-1], dp[i+2][j]) + nums[i];
                int right = min(dp[i+1][j-1], dp[i][j-2]) + nums[j];
                dp[i][j] = max(left, right);
            }
        }
        return 2 * dp[0][n-1] >= sum;
    }
};

备注：当手牌为奇数的时候，先手必胜。

4. 礼物的最大价值 「有的时候 我们可以直接在原数组上dp, 不需要空间」

剑指offer 47 :在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        // vector<vector<int>> dp(m, vector<int>(n));
        // // 我从左上角拿 那也意味着想要顺着边拿只能一直往下或一直往右.
        // dp[0][0] = grid[0][0];
        // for (int i = 1; i < m; ++i) dp[i][0] = dp[i-1][0] + grid[i][0];
        // for (int i = 1; i < n; ++i) dp[0][i] = dp[0][i-1] + grid[0][i];
        // for (int i = 1; i < m; ++i) {
        //     for (int j = 1; j < n; ++j) {
        //         dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        //     }
        // }
        // return dp[m-1][n-1];
        
        // 我们可以直接用grid数组本身代替dp数组 以下为优化方案. 
        for (int i = 1; i < m; ++i) grid[i][0] += grid[i-1][0];
        for (int i = 1; i < n; ++i) grid[0][i] += grid[0][i-1];
        for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) grid[i][j] += max(grid[i-1][j], grid[i][j-1]);
        return grid[m-1][n-1];
    }
};