动态规划算法学习

Posted Aug 14, 2024 Updated Mar 17, 2025

By Kurisu 53 min read

动态规划五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了；如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

动态规划基础

不同路径

问题：一个机器人位于一个 m x n 网格的左上角机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角）。问总共有多少条不同的路径？

动规五部曲来分析：

确定dp数组（dp table）以及下标的含义：dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
模拟推导

这题主要是初始化的方面卡住了，不够灵活变通。

代码示例：

  
class Solution {
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //初始化
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

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

整数拆分

问题：给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

动规五部曲来分析：

确定dp数组（dp table）以及下标的含义：dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
确定递推公式：可以从1遍历j，然后有两种渠道得到dp[i]，一个是j * (i - j) 直接相乘，一个是j * dp[i - j]，相当于是拆分(i - j)，dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))。可以这么理解，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘，如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了，取遍历过程最大的dp[i]。
只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，dp[0]dp[1]无实际意义。
dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。下标从小到大
举例推导dp数组。

这题卡在不知道该如何用动态规划处理多种拆分方式，学习到了通过dp[i - j] * j来拆分的方式。

代码示例：

  
class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}

不同的二叉搜索树

问题：给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

这题关注一下递推公式的推导就行了，也就是新加入的节点的左子树的种类*右子树的种类，dp[i] += dp[j - 1] * dp[i - j]

代码示例：

  
class Solution {
    public int numTrees(int n) {
        //初始化 dp 数组
        int[] dp = new int[n + 1];
        //初始化0个节点和1个节点的情况
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
                //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

背包问题

01背包

01背包理论基础

问题：有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动规五部曲分析：

确定dp数组以及下标的含义：需要用到二维数组，有两个维度需要表示，分别是：物品和背包容量。我们用二维数组dp[i][j]，i来表示物品、j表示背包容量，dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
递推公式：两种情况，对于新的dp来讲，涉及到要不要把对应物品放入。
不放物品则由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。
放入物品则还要考虑价值是否最高，由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值。
初始化：如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0；状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
遍历顺序：其实都可以，遍历物品更好理解一些。
举例推导。

代码示例：

  
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 处理输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] costs = new int[m];
        int[] values = new int[m];
        for (int i = 0; i < m; i++) {
            costs[i] = sc.nextInt();
        }
        for (int j = 0; j < m; j++) {
            values[j] = sc.nextInt();
        }
        // 调用方法输出
        System.out.println(MaxValue(costs, values, n));
    }
    
    public static int MaxValue(int[] costs, int[] values, int n) {
        // 取第0-i个物品，占据j空间时的最大价值
        int[][] dp = new int[costs.length][n+1];
        // 初始化
        for (int j = costs[0]; j <= n; j++) {
            dp[0][j] = values[0];
        }
        // 递推过程
        for(int i = 1; i < costs.length; i++) {
            for(int j = 0; j <= n; j++) {
                if (j < costs[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - costs[i]] + values[i]);
                }
            }
        }
        // 返回结果
        return dp[costs.length-1][n];
    }
}

01背包理论基础（滚动数组）

问题：仍然是上面的问题。

运用滚动数组实现对dp数组的降维。
递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，从中其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]); 直接去掉i这个维度，递推公式就变成了dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

除此之外，一维dp在遍历时需要倒序遍历，是为了保证物品i只被放入一次！

代码示例：

  
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 处理输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] costs = new int[m];
        int[] values = new int[m];
        for (int i = 0; i < m; i++) {
            costs[i] = sc.nextInt();
        }
        for (int j = 0; j < m; j++) {
            values[j] = sc.nextInt();
        }
        // 调用方法输出
        System.out.println(MaxValue(costs, values, n));
    }
    // 处理方法
    public static int MaxValue(int[] costs, int[] values, int n) {
        // 占据j空间时的最大价值
        int[] dp = new int[n+1];
        // 递推过程
        for(int i = 0; i < costs.length; i++) {
            for(int j = n; j >= costs[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
            }
        }
        // 返回结果
        return dp[n];
    }
}

分割等和子集

问题：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

本题的目标可以转化为集合里能否出现总和为 sum / 2 的子集，本题中每一个元素的数值既是重量，也是价值，只有确定了如下四点，才能把01背包问题套到本题上来：

背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

动规五部曲：

确定dp数组以及下标的含义： dp[j]表示容量为j的背包，所背的物品价值最大可以为dp[j]，套到本题，dp[j]表示背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。
递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
题目给的价值都是正整数那么非0下标都初始化为0就可以了。
如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
举例推导

代码示例：

  
class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < n; i++) {
            for(int j = target; j >= nums[i]; j--) {
                //物品 i 的重量是 nums[i]，其价值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
           
            //剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）
            if(dp[target] == target)
                return true;
        }
        return dp[target] == target;
    }
}

完全背包

完全背包理论基础

问题：和01背包的区别就是，同一个物品可以被重复选择。

01背包和完全背包唯一不同就是体现在遍历顺序上，所以就不去做动规五部曲了，我们直接针对遍历顺序经行分析！既然之前01背包为了不重放选择了使用倒序遍历，那对于完全背包问题，我们正序遍历即可。

代码示例：

  
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] costs = new int[N];
        int[] values = new int[N];
        for(int i = 0; i < N; i++) {
            costs[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }
        System.out.println(MaxValue(costs, values, N, V));
    }
    public static int MaxValue(int[] costs, int[] values, int N, int V) {
        int[] dp = new int[V + 1];
        for(int i = 0; i < N; i++) {
            for(int j = costs[i]; j <= V; j++)
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
        }
        return dp[V];
    }
}

零钱兑换II

问题：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

递推公式：求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];

此外，纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，故遍历顺序对结果没有影响。但这题，是要求凑成总和的组合数，外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况，这种遍历顺序中dp[j]里计算的是组合数；交换顺序计算的就是排列数。

代码示例：

  
class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

爬楼梯（进阶版）

问题：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

这道题也是一个完全背包问题，递推公式套入为dp[j] += dp[j -i];不同的是，这是一个求排列的问题，因为先上2再上1和先上1再上2是不同的方案，需要注意先遍历target，再遍历m步数。

代码示例：

  
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(Floor(n, m));
        
    }
    public static int Floor(int n, int m) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // 遍历背包
            for (int j = 1; j <= m; j++)  // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
        }
        return dp[n];
    }
}

零钱兑换

问题：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

完全背包问题的公式化处理基本没有太大问题了，这题主要是初始化和最后结果的处理没有考虑周全，为了保证能正常取Math.min，需要初始化dp数组为最大值，但dp[0]作为推导起点需要初始化为0；最后结果处理需要判断dp数组是否仍为初始化的最大值，如果还是最大值说明没有可能的方案。

代码示例：

  
class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历：完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

完全平方数

问题：给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

和零钱兑换问题是一样的，只不过value隐藏在平方数里了，递推公式变化为：dp[j] = min(dp[j - i * i] + 1, dp[j]);

代码示例：

  
class Solution {
    // 版本一，先遍历物品, 再遍历背包
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        //当和为0时，组合的个数为0
        dp[0] = 0;
        // 遍历物品
        for (int i = 1; i * i <= n; i++) {
            // 遍历背包
            for (int j = i * i; j <= n; j++) {
                //if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                //}
		//不需要這個if statement，因爲在完全平方數這一題不會有"湊不成"的狀況發生（ 一定可以用"1"來組成任何一個n），故comment掉這個if statement。
            }
        }
        return dp[n];
    }
}

单词拆分

问题：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

确定dp数组以及下标的含义：dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
确定递推公式：如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true，所以递推公式是if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
dp数组如何初始化：dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。
遍历顺序：本题是完全背包问题，字符串拼接是由顺序，所以这题是求排列数，要求先遍历背包，再遍历物品。
模拟推导

代码示例：（待补全）

多重背包

问题：在01背包问题的基础上，每一件物品有若干个。

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。多了一层针对同一种物品的遍历，其他和01背包问题完全一致。

代码示例：

  
import java.util.Scanner;
class multi_pack{
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);

        /**
         * bagWeight:背包容量
         * n:物品种类
         */
        int bagWeight, n;
        
        //获取用户输入数据，中间用空格隔开，回车键换行
        bagWeight = sc.nextInt();
        n = sc.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) weight[i] = sc.nextInt();
        for (int i = 0; i < n; i++) value[i] = sc.nextInt();
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();

        int[] dp = new int[bagWeight + 1];

        //先遍历物品再遍历背包，作为01背包处理
        for (int i = 0; i < n; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                //遍历每种物品的个数
                for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        System.out.println(dp[bagWeight]);
    }
}

打家劫舍

打家劫舍II

问题：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

和普通的打家劫舍问题的区别就是变成了环，要注意原头部尾部的处理，我们的解决方式是分类讨论，考虑不包含头尾的情况、只包含头的情况、只包含尾的情况。但实际上我们包含的范围也只是纳入考虑范围，不代表一定会选取，所以情况二情况三其实是包含了情况一的。

代码示例

  
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        if (len == 1)
            return nums[0];
        return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
    }

    int robAction(int[] nums, int start, int end) {
        int x = 0, y = 0, z = 0;
        for (int i = start; i < end; i++) {
            y = z;
            z = Math.max(y, x + nums[i]);
            x = y;
        }
        return z;
    }
}

打家劫舍 III

问题：小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

这题与以往动规都不同的是，本题是树形DP，要结合递归和树的遍历方式去解决这道题目，首先本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算，如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子。

确定递归函数的参数和返回值：这里我们要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。其实这里的返回数组就是dp数组，所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
确定终止条件：在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回，相当于是dp数组的初始化。
确定遍历顺序：如前面所说，采用后序遍历。
确定单层递归的逻辑：如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子。
举例推导dp数组。

代码示例：

  
    // 不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
    // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
    // Math.max(rob(root.right)[0], rob(root.right)[1])
    // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
    // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
    public int rob3(TreeNode root) {
        int[] res = robAction1(root);
        return Math.max(res[0], res[1]);
    }

    int[] robAction1(TreeNode root) {
        int res[] = new int[2];
        if (root == null)
            return res;

        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }

股票问题

买卖股票的最佳时机

问题：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

确定dp数组（dp table）以及下标的含义：dp[i][0] 表示第i天持有股票所得最多现金，dp[i][1] 表示第i天不持有股票所得最多现金。
确定递推公式：
如果第i天持有股票即dp[i][0]，第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]，第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]。
如果第i天不持有股票即dp[i][1]，第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]，第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]。
dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
dp数组如何初始化：dp[0][0] -= prices[0];dp[0][1] = 0;
从前向后遍历
举例推导

代码示例

  
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];
        int result = 0;
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[length - 1][1];
    }
}

买卖股票的最佳时机II

问题：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

与上一题的区别就在于，上题是一次买入卖出，而这题要尽可能多的完成交易，获取最大利润。

主要是递推公式有所区别了，上一题因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]，而本题第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]。区别就这些。

代码示例：

  
class Solution {
    // 实现1：二维数组存储
    // 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];     // 创建二维数组存储状态
        dp[0][0] = 0;                   // 初始状态
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);    // 第 i 天，没有股票
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第 i 天，持有股票
        }
        return dp[n - 1][0];    // 卖出股票收益高于持有股票收益，因此取[0]
    }
}

买卖股票的最佳时机III

问题：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

这道题相比于上一道限定了交易笔数，这意味着可以买卖一次，可以买卖两次，也可以不买卖。解决方法就是把二维数组的状态位拓展为多个状态，给出多个递推公式。dp[i][1]是第一次持有股票，dp[i][2]是第一次不持有股票，dp[i][3]是第二次持有股票，dp[i][4]是第二次不持有股票。

代码示例：

  
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;

        /*
         * 定义 5 种状态:
         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];

        for (int i = 1; i < len; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }

        return dp[len - 1][4];
    }
}

买卖股票的最佳时机IV

问题：给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

思想和上一题是一样的，就是多了更多的状态，需要采用循环来处理。

代码示例：

  
class Solution {
    public int maxProfit(int k, int[] prices) {
        int[][] dp = new int[prices.length][2*k + 1];
        for (int i = 1; i < k*2; i += 2) {
            dp[0][i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < k*2 - 1; j += 2) {
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[prices.length - 1][k*2];
    }
}

子序列问题

最长递增子序列

问题：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

这题主要是递推公式的推导，dp[i]即到i为止最长递增子序列的长度到底可以从哪些状态推出来。

注意这是一个子序列的问题，不要求连续，所以if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1); j是从0遍历到i。这题我一开始不理解的地方在于为什么不能直接返回dp[nums.length]，dp[i]的定义是以下标i结尾的子序列的最长长度，而不是考虑0~i的字符的子序列最长长度，要理解清楚这一点。

代码示例：

  
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length];
        int res = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}   

最长连续递增序列

问题：给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

这题和上一题的区别在于序列要是连续的，其实这样的话比上面更加简单，递推公式为dp[i] = dp[i-1] + 1。

代码示例：

  
    public static int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        int res = 1;
	//可以注意到，這邊的 i 是從 0 開始，所以會出現和卡哥的C++ code有差異的地方，在一些地方會看到有 i + 1 的偏移。
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                dp[i + 1] = dp[i] + 1;
            }
            res = res > dp[i + 1] ? res : dp[i + 1];
        }
        return res;
    }

最长重复子数组

问题：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

这道题目开始求公共部分问题了，考虑用二维dp来保存两个数组的信息。需要两个数组循环遍历，递推公式dp[i][j] = dp[i - 1][j - 1] + 1;

代码示例：

  
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int result = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        
        return result;
    }
}

最长公共子序列

问题：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

这道题就是从上面的连续变为了不连续，递推公式为，若遍历到的字符相等dp[i][j] = dp[i-1][j-1] + 1，不相等dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

代码示例：

  
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // char[] char1 = text1.toCharArray();
        // char[] char2 = text2.toCharArray();
	// 可以在一開始的時候就先把text1, text2 轉成char[]，之後就不需要有這麼多爲了處理字串的調整
	// 就可以和卡哥的code更一致
 	
        int[][] dp = new int[text1.length() + 1][text2.length() + 1]; // 先对dp数组做初始化操作
        for (int i = 1 ; i <= text1.length() ; i++) {
            char char1 = text1.charAt(i - 1);
            for (int j = 1; j <= text2.length(); j++) {
                char char2 = text2.charAt(j - 1);
                if (char1 == char2) { // 开始列出状态转移方程
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

编辑距离

问题：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

定义dp[i][j]为下标i结尾的word1和下标j结尾的word2所需最少操作数。对word1和word2进行循环遍历，当遍历到的字符相等时不需要任何操作，若不相等，则需要考虑是插入一个字符，删除一个字符还是替换一个字符。需要注意的是，word2添加一个元素，相当于word1删除一个元素，递推公式就为dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

代码示例：

  
public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 初始化
    for (int i = 1; i <= m; i++) {
        dp[i][0] =  i;
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 因为dp数组有效位从1开始
            // 所以当前遍历到的字符串的位置为i-1 | j-1
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
    }
    return dp[m][n];
}

回文子串

问题：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

按照往常的dp数组定义很难找到递推关系，我们选择布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
i和j遍历到的两个字符不相等，默认赋值为false，若相等，当i 与 j相同，同一个字符例如a，当然是回文子串；下标i 与 j相差为1，例如aa，也是回文子串；i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

根据递推公式，一定要i从大到小，j从i开始小到大遍历。

代码示例：

  
class Solution {
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        boolean[][] dp = new boolean[len][len];
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { //情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
}

学习, 算法

算法

This post is licensed under CC BY 4.0 by the author.

动态规划基础

不同路径

整数拆分

不同的二叉搜索树

背包问题

01背包

01背包理论基础

01背包理论基础（滚动数组）

分割等和子集

完全背包

完全背包理论基础

零钱兑换II

爬楼梯（进阶版）

零钱兑换

完全平方数

单词拆分

多重背包

打家劫舍

打家劫舍II

打家劫舍 III

股票问题

买卖股票的最佳时机

买卖股票的最佳时机II

买卖股票的最佳时机III

买卖股票的最佳时机IV

子序列问题

最长递增子序列

最长连续递增序列

最长重复子数组

最长公共子序列

编辑距离

回文子串

Trending Tags