动态规划
动态规划和递归都是见原问题拆成多个子问题然后求解，它们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
1
2
3
4
5
6
| 输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
|
示例 2：
1
2
3
4
5
6
7
| 输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
|
leetcode原题地址
解法
这道题是一道非常经典的题。我们今天尝试使用动态规划来解它。
$$
dp[n]=dp[n-1]+dp[n-2]
$$
到达第n阶楼梯的走法等于到达第n-1阶然后在走一阶加上到达n-2阶的走法然后再走两步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int climbStairs(int n) {
if(n<2){
return n;
}
int pre1=2;
int pre2=1;
for(int i=2;i<n;i++){
int cur=pre1+pre2;
pre2=pre1;
pre1=cur;
}
return pre1;
}
|
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
1
2
3
4
| 输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
|
示例 2:
1
2
3
4
| 输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
|
leetcode原题地址
解法
$$
dp[n]=max(dp[n-2]+nums[n],dp[n-1])
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int rob(int[] nums) {
int pre2=0;
int pre1=0;
for(int i=0;i<nums.length;i++){
int cur=Math.max(pre2+nums[i],pre1);
pre2=pre1;
pre1=cur;
}
return pre1;
}
|
213. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
1
2
3
| 输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
|
示例 2:
1
2
3
4
| 输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
|
leetcode原题地址
解法
这道题的原理和上一题类似，但是因为是环形的，所以第一家和最后一家只能选择一个偷。所以我们将这两个方案都计算一下，比较得到最佳方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public int rob(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
return Math.max(rob(nums,0,nums.length-2),rob(nums,1,nums.length-1));
}
private int rob(int[] nums,int start,int end){
int pre1=0;
int pre2=0;
for(int i=start;i<=end;i++){
int cur=Math.max(pre1,pre2+nums[i]);
pre2=pre1;
pre1=cur;
}
return pre1;
}
|
64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
1
2
3
4
5
6
7
8
| 输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
|
leetcode原题地址
解法
$$
dp[i,j]=grid[i,j]+min(dp[i+1,j],dp[i,j+1])
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int minPathSum(int[][] grid) {
int[] dp = new int[grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
dp[j] = grid[i][j] + dp[j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
dp[j] = grid[i][j] + dp[j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
else
dp[j] = grid[i][j];
}
}
return dp[0];
}
|
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径？
示例 1:
1
2
3
4
5
6
7
8
| 输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
|
示例 2:
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
leetcode原题地址
解法
$$
dp[i,j]=dp[i-1,j]+dp[i,j-1]
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public 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 j=0;j<n;j++){
dp[0][j]=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];
}
|
303. 区域和检索-数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
1
2
3
4
5
| 给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
|
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
leetcode原题地址
解法
求区间i-j的和，可以转换为sum[j+1]-sum[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private int[] sums;
public NumArray(int[] nums) {
sums=new int[nums.length+1];
for(int i=1;i<=nums.length;i++){
sums[i]=sums[i-1]+nums[i-1];
}
}
public int sumRange(int i, int j) {
return sums[j+1]-sums[i];
}
|
343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
1
2
3
| 输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
|
示例 2:
1
2
3
4
5
| 输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
|
leetcode原题地址
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int integerBreak(int n) {
int[] dp=new int[n+1];
dp[1]=dp[2]=1;
for(int i=3;i<=n;i++){
for(int j=0;j<i;j++){
dp[i]=Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
}
}
return dp[n];
}
|
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
1
2
3
| 输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
|
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
leetcode原题地址
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int lengthOfLIS(int[] nums) {
int[] dp=new int[nums.length];
for(int i=0;i<nums.length;i++){
int max=1;
for(int j=0;j<nums.length;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(max,dp[j]+1);
}
}
dp[i]=max;
}
int ret=0;
for(int i=0;i<dp.length;i++){
if(dp[i]>ret){
ret =dp[i];
}
}
return ret;
}
|