动态规划专题

——鸽了两天了，这几天事情很多，加之自己的状态也有些差，看题解写了题，但没来得及总结博客。
——有个题实质不难，看了题解后自己去写，题目都没读清，脑瓜子不清醒，硬是在那看了一个多钟，以为哪里出bug了，离谱了…这几天尽快调整状态找回节奏吧！
——哭了，qaq…

一、基础动规

1. 斐波那契数

题目链接：509. 斐波那契数 - 力扣（LeetCode）

Code

递归求解：

class Solution {
    public int fib(int n) {
        return dfs(n);
    }
    public int dfs(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        return dfs(n - 1) + dfs(n - 2);
    }
}

动态规划：

class Solution {
    int[] f = new int[40];
    public int fib(int n) {
        f[0] = 0;
        f[1] = 1;
        for(int i = 2; i <= n; i ++) f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
}

2. 爬楼梯 - 力扣

题目链接：70. 爬楼梯 - 力扣（LeetCode）

状态转移方程：f[i] = f[i - 1] + f[i - 2]

Code

class Solution {
    int[] f = new int[110];
    public int climbStairs(int n) {
        f[1] = 1;
        f[2] = 2;
        for(int i = 3; i <= n; i ++) f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
}

3. 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯 - 力扣（LeetCode）

到第n层得最小花费 = min(到第n-1层的最小花费，到第n-2层的最小花费) + 当前层花费

状态表示f[i]：走到第i的最小花费

状态转移：f[i] = Math.min(f[i - 1], f[i - 2]) + cost[i]

Code

class Solution {
    int[] f = new int[1010];
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        f[0] = cost[0];
        f[1] = cost[1];
        for(int i = 2; i < n ; i ++)
            f[i] = Math.min(f[i - 1], f[i - 2]) + cost[i];
        // 到达最后一层有两种选择，选最小得即可
        return Math.min(f[n - 1], f[n - 2]);    
    }
}

4. 不同路径

题目链接：62. 不同路径 - 力扣（LeetCode）

递归：超时

class Solution {
    int m;
    int n;
    public int uniquePaths(int _m, int _n) {
        m = _m;
        n = _n;
        return dfs(1, 1);
    }
    public int dfs(int x, int y){
        if(x > m || y > n){
            return 0;
        }
        if(x == m && y == n){
            return 1;
        }
        return dfs(x + 1, y) + dfs(x, y + 1);
    }
}

class Solution {
    int m;
    int n;
    int res = 0;
    public int uniquePaths(int _m, int _n) {
        m = _m;
        n = _n;
        dfs(1, 1);
        return res;
    }
    public void dfs(int x, int y){
        if(x > m || y > n){
            return ;
        }
        if(x == m && y == n){
            res ++;
            return ;
        }
        dfs(x + 1, y);
        dfs(x, y + 1);
    }
}

动态规划：

状态表示f[i][j]：从(1, 1)走到（i， j）的方案的集合

属性：计数 count

状态转移：f[i][j] = f[i - 1][j] + f[i][j - 1]

初始化：

for(int i = 0; i < n; i ++) f[0][i] = 1;
for(int i = 0; i < m; i ++) f[i][0] = 1;

Code

class Solution {
    int[][] f = new int[110][110];
    public int uniquePaths(int m, int n) {
        for(int i = 0; i < n; i ++) f[0][i] = 1;
        for(int i = 0; i < m; i ++) f[i][0] = 1;

        for(int i = 1; i < m; i ++){
            for(int j = 1; j < n; j ++){
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

5.不同路径 II

题目链接：63. 不同路径 II - 力扣（LeetCode）

这一题和上一题的区别是，本题多了障碍物！

题目链接：980. 不同路径 III - 力扣（LeetCode）

动态规划：

状态表示f[i][j]：从起点走到（i， j）的方案的集合

属性：计数 count

状态转移：

• 当遇到障碍物时，说明无法到达(i,j)，即f[i][j] = 0，当我们枚举时遇到障碍物直接跳过即。

• f[i][j] = f[i - 1][j] + f[i][j - 1]

初始化：

for(int i = 0; i < n && obstacleGrid[0][i] == 0; i ++) f[0][i] = 1;
// 当遇到障碍物时循环就会结束了！
for(int i = 0; i < m && obstacleGrid[0][i] == 0; i ++) f[i][0] = 1;

Code

class Solution {
    int[][] f = new int [110][110];
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        // 初始化（同不同路径I） 但当遇到障碍物时当前位置和后面都应该为0，反之为1
        for(int i = 0; i < m && obstacleGrid[0][i] == 0; i ++) f[0][i] = 1;
        for(int i = 0; i < n && obstacleGrid[i][0] == 0; i ++) f[i][0] = 1;

        for(int i = 1; i < n; i ++){
            for(int j = 1; j < m; j ++){
                if(obstacleGrid[i][j] == 0)// 若是障碍物就跳过
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[n - 1][m - 1];
    }
}

6. 不同路径 III

题目链接：980. 不同路径 III - 力扣（LeetCode）

思路：本题上下左右四种状态而且要求所有的空格格子都要走一遍，我们不好使用动态规划，为此我们可以用回溯进行枚举所有满足条件的可能路线。

Code

class Solution {
    int emptyCount = 0;
    int n, m;
    int res = 0;
    int xx, yy;
    boolean[][] st = new boolean[30][30];
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    public int uniquePathsIII(int[][] g) {
        n = g.length;
        m = g[0].length;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j ++){
                if(g[i][j] == 1){
                    xx = i;
                    yy = j;
                }
                else if(g[i][j] == 0){
                    emptyCount ++;
                }
            }
        }
        st[xx][yy] = true;
        dfs(g, xx, yy, 0);
        return res;
    }
    public void dfs(int[][] g, int x, int y, int count){

        if(g[x][y] == 2){
            if(count == emptyCount + 1){// 注意了：起点也算是路径必须经过的一点
                res ++;
            }
            return ;
        }
       
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            // 越界、障碍物、或者被选过了
            if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] == -1 || st[a][b] == true){
                continue;
            }
            // System.out.println(a + " " + b);
            st[a][b] = true;
            dfs(g, a, b, count + 1);
            st[a][b] = false;// 回溯
        }

    }
}

7.不同的二叉搜索树

题目链接：95. 不同的二叉搜索树 II - 力扣（LeetCode）

思路：由于是1~n，枚举所有根节点的所有可能，[l, i ,r]，二叉搜索树的左子树[l, i - 1]，右子树[i + 1, r]，然后枚举左右子树的所有拼接可能（一个root有左右子树构造成功的二叉搜索树可能有多种情况）

• 枚举所有根节点的所有可能
• 递归构建左右子树
• 给root节点枚举所有左右子树的组合

Code

class Solution {
    public List<TreeNode> generateTrees(int n) {
        return build(1, n);
    }
    public List<TreeNode> build(int l, int r){
        List<TreeNode> res = new ArrayList<>();
        if(l > r){
            res.add(null);
            return res;
        }
         
        //枚举所有根 递归构建左右子树
        for(int i = l; i <= r; i ++){
            List<TreeNode> lnodes = build(l, i - 1);
            List<TreeNode> rnodes = build(i + 1, r);
            // 枚举左右子树能够构成二叉搜索树的组合
            for(int j = 0; j < lnodes.size(); j ++){
                for(int k = 0; k < rnodes.size(); k ++){
                    TreeNode root = new TreeNode(i);// 根
                    root.left = lnodes.get(j);
                    root.right = rnodes.get(k);
                    res.add(root);
                }
            }
        }
        return res;
    }
}

8.不同的二叉搜索树 II

题目链接：96. 不同的二叉搜索树 - 力扣（LeetCode）

思路：本题只让我们计数，并没有让我们求出所有方案的路径。

根据上一题的解法，我们可以用动态规划来实现：

状态表示：f[i]：表示区间长度为i所构成的不同二叉搜索树的集合

属性：count

由上一题，我们同枚举所有根来明确它的左右子树，本题也同样如此：

[1, j ,i]，j表示根节点，那么

• 左子树所构成的不同二叉搜索树的方案组合：f[j - 1]
• 右子树所构成的不同二叉搜索树的方案组合：f[i- j]

状态计算：综上区间长度为i所构成的不同二叉搜索树的集合数量：f[i] += f[j - 1] * f[i - j]

Code

class Solution {
    int[] f = new int[30];
    public int numTrees(int n) {
        f[0] = 1;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= i; j ++){
                f[i] += (f[j - 1] * f[i - j]);
            }   
        }
        return f[n];
    }
}

二、背包问题（模板）

看之前博客的总结吧，懒得打字了：背包问题模型总结_塔塔开!!!的博客-CSDN博客_背包问题模型

01背包

01背包：每一个物品只能选一次，选或者不选

状态标识：f[i][j]：所有只考虑前i个物品，且总体积不超j的所有选法的集合

属性：Max

状态计算：f[i][j]

• 不选第i个物品：f[i][j] = f[i - 1][j]
• 选第i个物品：f[i][j] = f[i - 1][j - v[i]] + w[i]

二维：

	for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]){
                f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }

一维：

	for(int i = 1; i <= n; i ++){
        for(int j = m; j >= v[i]; j --){
            f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
        }
    }

逆序枚举体积：f[i][j] = Math.max(f[i][j],f[i - 1][j - v[i]]+ w[i]);，用到上一层的状态时,从大到小枚举, 反之从小到大哦

完全背包

…

多重背包

…

分组背包

…

三、01背包

9. 分割等和子集

题目链接：416. 分割等和子集 - 力扣（LeetCode）

思路：题目让我们构造两个子集使得两个子集的和相等，其实就是让我们构造其中一个子集的和是否等于sum / 2，若存在说明能分割等和子集。如果sum为奇数，是不能分割等和子集的。

换句话说，题目就是让我们从nums[]中选择一些物品，使得物品的总和恰好为target(sum / 2)，为此可以转化为01背包问题

Code

二维：

class Solution {
    // f[i][j]：从前i个物品中选 总和恰好为j
    // 属性：boolean
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2 == 1){
            return false;
        }
        int m = sum / 2;
        boolean[][] f = new boolean[n + 10][m + 10];
        f[0][0] = true;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                f[i][j] = f[i - 1][j];// 不选
                if(j >= nums[i - 1]){
                    f[i][j] = f[i][j] || f[i - 1][j - nums[i - 1]];// 选
                }
            }
        }
        return f[n][m];
    }
}

一维：

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2 == 1) return false;

        int m = sum / 2;
        boolean[] f = new boolean[m + 10];
        f[0] = true;
        for(int i = 1; i <= n; i ++){
            for(int j = m; j >= nums[i - 1]; j --){
                f[j] |= f[j - nums[i - 1]];
            }
        }
        return f[m];
    }
}

10. 一和零

题目链接：474. 一和零 - 力扣（LeetCode）

Code

思路：每个字符串可以选或者不选，与常规的背包问题不同的是本题的背包有两个容量限制（物品的体积就是每一个字符串0和1的个数）：

• 0 的数目不超过 m；
• 1 的数目不超过 n 。

状态表示：f[i][j][k]：从前i个物品中选，0的个数不超过j，1的个数不超过k的所有集合

属性：Max

状态计算：f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - zcnt][k - ocnt] + 1)

初始状态： dp[0][j][k] 表示从前 0 个字符串（为空集合）中选出若干个（其实只有 0 个）字符串时的状态值，显然此时均满足 0 的数目不超过 j、1 的数目不超过 k，且有 dp[0][j][k] = 0 （ 0 个字符串）。

dp[i][0][0]=0 ：前 i 个字符串中只有选出 0 个字符串才有可能使得其中0和1的数目均不超过 0。这在程序迭代实现中已有体现，在此无需提前重复定义。

Code

三维：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int all = strs.length;
        int[][][] f = new int[all + 10][m + 10][n + 10];
        for(int i = 0; i < all; i ++){
            int zero = 0;
            int one = 0;
            for(char c : strs[i].toCharArray()){
                if(c == '0') zero ++;
                else one ++;
            }
            for(int j = 0; j <= m; j ++){
                for(int k = 0; k <= n; k ++){
                    // 由于物品是从下标0开始枚举的，而实际是1~all枚举 为此i + 1
                    f[i + 1][j][k] = f[1 + i - 1][j][k];
                    if(j >= zero && k >= one){
                        f[i + 1][j][k] = Math.max(f[i + 1][j][k], f[1 + i - 1][j - zero][k - one] + 1);
                    }
                }
            }
        }
        return f[all][m][n];
    }
}

二维：

状态表示：f[j][k]：0的个数不超过j，1的个数不超过k的所有集合

属性：Max

状态计算：f[j][k] = max([j][k], f[j - zcnt][k - ocnt] + 1)

Code

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int all = strs.length;
        int[][] f = new int[m + 10][n + 10];
        for(int i = 0; i < all; i ++){
            int zero = 0;
            int one = 0;
            for(char c : strs[i].toCharArray()){
                if(c == '0') zero ++;
                else one ++;
            }
            for(int j = m; j >= zero; j --){
                for(int k = n; k >= one; k --){
                    // 由于物品是从下标0开始枚举的，而实际是1~all枚举 为此i + 1
                    if(j >= zero && k >= one){
                        f[j][k] = Math.max(f[j][k], f[j - zero][k - one] + 1);
                    }
                }
            }
        }
        return f[m][n];
    }
}

11.目标和

题目链接：

思路：每个数前面加+ 或者 -可以联想01背包，要么0要么1

我们将数组分为两部分，一部分为正数的p，一部分为负数的ne，

我们想要sum(p) + sum(ne) == S，

而数组的和是已知的即sum(p) + sum(ne) == sum，

两式相加化简得sum(p) = (sum + S) / 2 = targrt，

也就是说我们要从nums[]里边选几个数使其和为target，

于是就转换为求容量恰好为taeget的01背包问题。

特判：

• 如果S > sum 或者 S < -sum则不可能实现
• 如果(sum + S)为奇数（不是正整除），也不能实现

返回0

状态表示：f[j]：从前i个物品中选，使得总和恰好j的所有集合

属性：count

状态计算：f[i][j] = f[i - 1][j] + f[i - 1][j - vi]，优化为一维的f[j] += f[i - 1][j - vi]

初始化：f[0] = 1，体积为0（和为0），那就是一个物品都不放，有一种方案。

Code

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for(int x : nums) sum += x;
        if(S > sum || (S + sum) % 2 == 1 || S < -sum){// [100] -200
            return 0;
        }

        int target = (sum + S) / 2;
        int[] f = new int[target + 10];
        f[0] = 1;
        for(int v : nums){
            for(int j = target; j >= v; j --){
                f[j] += f[j - v];
            }
        }
        return f[target];
    }
}

12 . 最后一块石头的重量

题目链接：1046. 最后一块石头的重量 - 力扣（LeetCode）

思路：贪心题，每次选择两个最大的合并，然后放入…，可以用一个维护大根堆的优先队列来实现。

Code

class Solution {
    //自定义比较器 维护大根堆
    class MyComparator implements Comparator<Integer>{
        public int compare(Integer o1, Integer o2){
            return o2 - o1;
        }
    }

    public int lastStoneWeight(int[] stones) {
        Queue<Integer> q = new PriorityQueue<>(new MyComparator());
        for(int x : stones) q.offer(x);

        while(q.size() > 1){
            int x = q.poll();
            int y = q.poll();

            int tmp = Math.abs(x - y);
            if(tmp > 0) q.offer(tmp);
        }
        return q.size() == 1 ? q.peek() : 0;
    }
}

13. 最后一块石头的重量 II

题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

这题和上一题的区别是，本题选取两块石头的顺序是任意的！

思路：最后合并会有两种情况：

• 剩下0块：结果为0
• 剩下一块

我们从整体考虑，将stones[]划分为两个集合，即 【】- 【】= min，当两个集合的和一样时，min就为0（情况1），那如何使得最后的那一块石头（情况2）越小越好呢？------ 不难得出 两个两个集合总和越平均越好，即尽量接近于各占一半（hlaf+ —— half-）———— 我们就取一半（跟分割等和子集有些相像）

状态表示：f[j]：表示容量（这里说容量更形象，其实就是重量）为j的背包，**最多（至多）**可以背f[j]这么重的石头。(从stones[]中选一些物品，使得至多装满（<=）half)

状态计算：f[j] = max(f[j], f[j - stones[i]] + stones[i])

最后一块石头的的最小重量：sum - 2 * f[halft]

Code

一维：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int x : stones) sum += x;

        int half = sum / 2;
        int f[] = new int [half + 1];
        for(int i = 1; i <= n; i ++){
            for(int j = half; j >= stones[i - 1]; j --){
                f[j] = Math.max(f[j], f[j - stones[i - 1]] + stones[i - 1]);
            }
        }
        return sum - f[half] - f[half];
    }
}