「动态规划」告诉我们求解一个问题，可以不直接求解这个问题，而是去思考这个问题最开始（规模最小的时候）的时候是什么样子，然后通过递推的方式，一步一步得到结果，直到问题得到解决，这是一种「自下而上」的思想。
而我们熟悉的「递归」方法，是一种「自上而下」的思想。这两种思想在绝大多数情况下，都能够帮助我们解决问题。而「动态」告诉我们「自上而下」「自下而上」都可以解决这一类问题。在这里给大家一个提示，在我们这门课程里介绍的绝大多数「动态规划」的问题，都可以使用「自底向上」的思路解决，树形 dp 等情况除外。
对于可以使用「动态规划」解决的问题，主要有下面三个特点：重复子问题，最优子结构，无后效性，下面分别介绍分析。
1、重复子问题
也叫「重复子问题」，从「斐波拉契数列」求解的问题中，我们知道，如果递归地去这个问题，会遇到很多「重复子问题」。这些子问题不应该被重复计算。
509. 斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
class Solution {public int fib(int N) {if (N < 2) {return N;}int[] memo = new int[N+1];Arrays.fill(memo, -1);return fib(N, memo);}public int fib(int n, int[] memo) {if (n == 0) {return 0;}if (n == 1) {return 1;}if (memo[n] == -1) {memo[n] = fib(n - 1) + fib(n - 2);}return memo[n];}}
上面「递归」求解的过程是「自底向上」的过程，而「动态规划」告诉我们一种求解问题的思路：「自底向上」，事实上，我们人在计算的时候，更多会这样去计算。
- 「自上而下」和 「自底向上」的解法通常都可以称为「动态规划」；
- 如果没有学习过「动态规划」，通过「递归」求解，应该需要知道做了大量重复计算，因此需要加入缓存，这种做法叫「记忆化递归」或者「记忆化搜索」；
- 而使用「自底向上」的思路可以解决在入门阶段的绝大多数「动态规划」问题，我们就是去想一下，这个问题最开始的时候是什么样子，而不是直接去解决这个问题，请大家在练习的过程中逐渐体会这个思路。
因为有「重复子问题」，我们在「自底向上」求解的过程中，通过先解决更小规模的问题，在处理更大规模的问题的时候，直接使用了更小规模问题的结果，进而原问题得到了解决。
class Solution {
public int fib(int N) {
if (N < 2) {
return N;
}
int[] dp = new int[N+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
}
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
思路：
每次为 1 或 2 个台阶，则容易得出要到达 i，可以从 i-1 爬 1 个台阶，也可以从 i-2 爬 2 个台阶。
class Solution {
public int climbStairs(int n) {
if (n <= 1) return 1;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
}
2、最优子结构
求解子问题得到的最优解，组成了规模更大的原问题的最优解，这样的动态规划问题，我们称之为具有「最优子结构」。
动态规划问题通常应用的场景是：我们直接求解这个问题感觉难度较大，但是我们把这个问题拆分为规模更小的问题的时候，这个问题的解通常也就能够找到，这样的解决问题的实现通常都要借助递归来实现。
第 1 步：定义「状态」dp[i]：凑齐总价值 i 需要的最少硬币数，状态就是问的问题。
第 2 步：写出「状态转移方程」
所谓「状态转移方程」，其实就是「最优子结构」。
dp[amount] = min(1 + dp[amount - coin[i]]) for i in [0, len - 1] if coin[i] <= amount
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
for (int i = 1; i <= amount; i++) {
dp[i] = amount + 1;
}
dp[0] = 0;
for (int i = 1; i <= amount; i++ ) {
int cur = 0;
for (int j = 0; j < coins.length; j++) {
if (coins[j] > i) continue;
cur = 1 + dp[i - coins[j]];
dp[i] = Math.min(cur, dp[i]);
}
}
if (dp[amount] <= amount) {
return dp[amount];
} else {
return -1;
}
}
}
343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
思路：
根据提示，计算7到10的结果，找规律。发现从7开始满足dp[i] = dp[i - 3] * 3;。
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
if (n == 5) return 6;
if (n == 6) return 9;
dp[4] = 4;
dp[5] = 6;
dp[6] = 9;
for (int i = 7; i <= n; i++) {
dp[i] = dp[i - 3] * 3;
}
return dp[n];
}
}
3、无后效性
- 在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。
- 某阶段状态一旦确定，就不受之后阶段的决策影响。
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
思路：
题目只问最优值，并没有问最优解，因此绝大多数情况下可以考虑使用「动态规划」的方法。
如果我们直接将问题的问法定义成状态，会发现，当前这个房子「偷」和「不偷」会影响到后面的房子「偷」与「不偷」。
一般的情况是，只要有约束，就可以增加一个维度消除这种约束带来的影响，还是上一节和大家介绍的方法：把「状态」定义得清楚、准确，「状态转移方程」就容易得到了。
第 1 步：设计状态
「状态」这个词可以理解为「记录了求解问题到了哪一个阶段」。
由于当前这一个房屋是否有两种选择：（1）偷；（2）不偷。
dp[i][0] 表示：考虑区间 [0，i] ，并且下标为 i 的这个房间偷，能够偷窃到的最高金额；dp[i][1] 表示：考虑区间 [0，i] ，并且下标为 i 的这个房间不偷，能够偷窃到的最高金额。
说明：这个定义是有前缀性质的，即当前的状态值考虑了（或者说综合了）之前的相关的状态值，第 2 维保存了当前最优值的决策，这种通过增加维度，消除后效性的操作在「动态规划」问题里是非常常见的。
强调：
无后效性的理解：1、后面的决策不会影响到前面的决策； 2、之前的状态怎么来的并不重要。
再联系状态的定义：状态是一个概括的值，这个值是怎么来的，并不记录。因为状态定义更细致，后面的决策才不会影响到前面的决策。
第 2 步：状态转移方程
「状态转移方程」可以理解为「不同阶段之间的联系」。
今天只和昨天的状态相关，依然是分类讨论：
- 下标为
i的房屋不偷：或者是上一间不偷，或者是上一间偷，取二者最大值，即：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])； - 下标为
i的房屋偷：只需要从上一间不偷，这一间偷，即：dp[i][1] = dp[i - 1][0] + nums[i]。
第 3 步：考虑初始化
从第 2 天开始，每天的状态值只与前一天有关，因此第 1 天就只好老老实实算了。好在不难判断：dp[0][0] = 0 与 dp[0][1] = nums[0]；
这里有一种技巧，可以把状态数组多设置一行，这样可以减少对第 1 天的初始化，这样的代码把第 1 天的情况考虑了进去，但编码的时候要注意状态数组下标的设置， 请见题解最后的「参考代码 3」。
第 4 步：考虑输出
由于状态值的定义是前缀性质的，因此最后一天的状态值就考虑了之前所有的天数的情况。下标为 len - 1 这个房屋可以偷，也可以不偷，取二者最大值。
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (len <= 1) {
return len == 0 ? 0 : nums[0];
}
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
int r1 = 0, r2 = 0, res = Math.max(dp[0], dp[1]);
for (int i = 2; i < len; i++) {
r1 = dp[i-2] + nums[i];
r2 = dp[i-1];
dp[i] = Math.max(r1, r2);
res = Math.max(res, dp[i]);
}
return res;
}
}
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
思路：
对于首尾的情况，一共可以分为4种
1、首尾都不偷；
2、偷首不偷尾；
3、偷尾不偷首；
4、首尾都偷；（排除）
显然只要能够排除第4种情况，就能得到正确答案，可以采用两次dp，一次从0偷到n-1，一次从1偷到n，返回两次dp中的最大值即可。
1、dp定义：
dp[i] = x：从第 i 间房开始偷，小偷所能得到的最大金额
2、状态：
①、第 i 间房不偷，则去第 i + 1 间房看看，dp[i] = dp[i+1]
②、第 i 间房偷，则去第 i + 2 间房看看，dp[i] = dp[i + 2] + nums[i];
3、状态转移方程
dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]);
4、初态：dp[n] = 0
5、终态：dp1[0], dp2[1]
其中，dp1[i]表示从0偷到n-1号房，dp2[i]表示从1偷到n号房。注意数组长度≤2的情况。
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (len < 2) {
return len == 1 ? nums[0] : 0;
}
int[] dp1 = new int[len]; // 0 -> n-2
int[] dp2 = new int[len]; // 1 -> n
int res = Math.max(nums[0], nums[1]);
dp1[0] = nums[0];
dp1[1] = nums[0];
for (int i = 2; i < len - 1; i++) {
dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]);
res = Math.max(res, dp1[i]);
}
dp2[0] = 0;
dp2[1] = nums[1];
for (int i = 2; i < len; i++) {
dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
res = Math.max(res, dp2[i]);
}
return res;
}
练习：
62. 不同路径
思路：
推出状态转移方程。因为移动的方向只能为向下和向右，因此要走到坐标 (i, j)，可以从上方下来，也可以从左边过来，所以到该坐标的路径总数是二者之和。
63. 不同路径 II
思路：
和之前的题目类似，增加对障碍物的判断，如果某点有障碍物，则该点不可到达，因此其路径总数为 0。
64. 最小路径和
思路：
和不同路径类似。令dp[i][j]表示到grid[i][j]的最短路径。可以直接在 grid 数组上操作，节约空间。
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][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 j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
优化：
滚动数组空间优化。将二维dp优化成一维dp。
我们观察发现，dp[i][j]只和同行/列的上一个状态有关，这里就可以使用滚动数组将空间复杂度降低到O(n)，我们令dp的长度等于n，此时dp只保留二维dp的一行数据，dp[j]处的值未更新时，对应二维dp的dp[i-1][j]的状态即同列的上一个状态，而dp[j-1]是更新过的状态对应二维dp的dp[i][j-1]的状态即同行的上一个状态。
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
dp[0] = grid[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0 && i > 0) {
dp[j] += grid[i][j];
} else if (i == 0 && j > 0) {
dp[j] = dp[j - 1] + grid[i][j];
} else if (j > 0) {
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
}
return dp[n - 1];
}
}
120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
思路：
关键的地方在于三角形「从上到下」和「从下到上」思考的方向的不同。
1、从上到下：最边上的点只能从最边上的点走过来；
2、从下到上：每一点都有两个孩子：左孩子和右孩子，可以少掉很多讨论。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();
int[] dp = new int[len + 1];
for (int i = len - 1; i >= 0; i--) {
for (int j = 0; j < i + 1; j++) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
class Solution {
public int numDecodings(String s) {
int len = s.length();
char[] sarr = s.toCharArray();
int[] dp = new int[len];
if (sarr[0] == '0') {
dp[0] = 0;
} else {
dp[0] = 1;
}
for (int i = 1; i < len; i++) {
int count = 0;
char cur = sarr[i];
if (cur != '0') {
count += dp[i - 1];
}
int pre = Integer.parseInt(s.substring(i - 1, i + 1));
if (pre >= 10 && pre <= 26) {
if (i - 2 < 0) {
count++;
} else {
count += dp[i - 2];
}
}
dp[i] = count;
}
return dp[len-1];
}
}
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路：
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0) return 0;
int res = 1, n = nums.length;
int i, j;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(j = 1; j < n; j++) {
for(i = 0; i < j; i++) {
if(nums[j] > nums[i]) {
dp[j] = Math.max(dp[i]+1, dp[j]);
}
}
res = Math.max(dp[j], res);
}
return res;
}
}
若有收获，就点个赞吧
0 人点赞
