1. 前言
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，坑呢会有许多可行解，每一个解都对应一个值，我们希望找到具有最优值的解。动态规划算法和分治算法类似，
其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
2. 动态规划相关题目
递归和动态规划都是将原问题拆成多个子问题然后求解，它们之间最本质的区别是：动态规划保存了子问题的解，避免重复计算。
2.1 斐波那契数列
爬楼梯
题目描述
有N阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
解题思路：
定一个数组dp存储上楼梯的方法数（下标从1开始）， dp[i]表示走到第i个楼梯的方法数。
第i个楼梯可以从第i-1 和 i-2 个楼梯再走一步到达，走到第i个楼梯的方法数为走到第i-1个和第i-2个楼梯的方法数之和，考虑到dp[i]只与dp[i-1]和dp[i-2]有关，因此可以只用两个变量来存储dp[i-1]和dp[i-2]，使得原来的O(N)空间复杂度优化为O(1)
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
* 斐波那契数列 - 爬楼梯
* @param n 楼梯数
*/
public static int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2;
for (int i = 2; i < n; i++) {
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
强盗抢劫
题目描述
抢劫一排住户，但是不能抢邻近住户，求最大抢劫量
解题思路
定义dp数组用来存储最大抢劫量，其中dp[i]表示抢到第i个住户时的最大抢劫量，由于不能抢劫邻近住户，因此如果抢劫了第i个住户，那么只能抢劫i-2或者i-3的住户
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/**
* 斐波那契数列 - 强盗抢劫
*/
public static int rob(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
int pre3 = 0, pre2 = 0, pre1 = 0;
for (int num : nums) {
int cur = Math.max(pre2, pre3) + num;
pre3 = pre2;
pre2 = pre1;
pre1 = cur;
}
return Math.max(pre1, pre2);
}
2.2 矩阵路径
矩阵的最小路径之和
题目描述
求从矩阵的左上角到右下角的最小路径之和，每次只能向右和向下移动
解题思路
[ [1,3,1],[1,5,1],[4,2,1]] Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
* 矩阵路径- 矩阵的最小路径之和
*/
public static int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
if (i == 0) {
dp[j] = dp[j - 1];
} else {
dp[j] = Math.min(dp[j - 1], dp[j]);
}
dp[j] += grid[i][j];
}
}
return dp[n - 1];
}
矩阵的总路径数
- 题目描述
统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
* 矩阵路径- 矩阵的总路径数
*/
public static int uniquePaths(int m, int n){
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
public static int uniquePaths2(int m, int n) {
int S = m + n - 2; // 总共的移动次数
int D = m - 1; // 向下的移动次数
long ret = 1;
for (int i = 1; i <= D; i++) {
ret = ret * (S - D + i) / i;
}
return (int) ret;
}
