动态规划
70. 爬楼梯
难度简单882 收藏 分享 切换为英文 关注 反馈
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：* 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶</pre>
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶</pre>
class Solution {
public int climbStairs(int n) {
if(n==0 ||n==1)
return 1;
return climbStairs(n-1)+climbStairs(n-2);
}
}
这个方法不行，耗时间，leetcode能通过测试用例，但是提交通过不了。
class Solution {
public int climbStairs(int n) {
int [] a=new int[n+1];
a[0]=1;
a[1]=1;
for(int i=2;i<=n;i++)
a[i]=a[i-1]+a[i-2];
return a[n];
}
}
343. 整数拆分
难度中等170 收藏 分享 切换为英文 关注 反馈
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。</pre>
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。</pre>
**说明: **你可以假设 *n *不小于 2 且不大于 58。
class Solution {
public int integerBreak(int n) {
return breakint(n);
}
//将n至少分隔两部分
int breakint(int n){
if(n==1)
return 1;
int res=-1;
for(int i=1;i<=n-1;i++)
{//i+(n-i)
res=max3(res,i*(n-i),i*breakint(n-i));
}
return res;
}
int max3(int a,int b,int c){
return Math.max(a,Math.max(b,c));
}
}
用递归还是超过时间范围
使用记忆化搜索
class Solution {
int []memo;
public int integerBreak(int n) {
memo=new int [n+1];
return breakint(n);
}
//将n至少分隔两部分
int breakint(int n){
if(n==1)
return 1;
if(memo[n]!=0)
return memo[n];
int res=-1;
for(int i=1;i<=n-1;i++)
{//i+(n-i)
res=max3(res,i*(n-i),i*breakint(n-i));
}
memo[n]=res;
return res;
}
int max3(int a,int b,int c){
return Math.max(a,Math.max(b,c));
}
}
使用动态规划算法
class Solution {
int []memo;
public int integerBreak(int n) {
return breakint(n);
}
//将n至少分隔两部分
int breakint(int n){
memo=new int [n+1];//memo[i]表示将数值i分割后得到的最大乘积
memo[1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i-1;j++)
memo[i]=max3( j*(i-j),j*memo[i-j],memo[i]);
return memo[n];
}
int max3(int a,int b,int c){
return Math.max(a,Math.max(b,c));
}
}
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。</pre>
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
class Solution {
int [] memo;
public int rob(int[] nums) {
memo=new int[nums.length];
Arrays.fill(memo, -1);
return tryrob(nums, 0);
}
private int tryrob(int[] nums, int index){
if(index>=nums.length)
return 0;
if(memo[index]!=-1)
return memo[index];
int res=0;
for(int i=index ;i < nums.length;i++){
res=Math.max((nums[i]+tryrob(nums,i+2)),res);
}
memo[index]=res;
return res;
}
}
这是我看到的题的评论的动态规划解法
/**
* 方式二：动态规划
*/
public int rob2(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
// memo[i] 表示考虑抢劫 nums[i...n-1] 所能获得最大收益（不是说一定从 i 开始抢劫）
int[] memo = new int[n];
// 先考虑最简单的情况
memo[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
// memo[i] 的取值在考虑抢劫 i 号房子和不考虑抢劫之间取最大值
memo[i] = Math.max(nums[i] + (i + 2 >= n ? 0 : memo[i + 2]), nums[i + 1] + (i + 3 >= n ? 0 : memo[i + 3]));
}
return memo[0];
}
/**
* 动态规划简化版
*/
public int rob(int[] nums) {
int n = nums.length;
if (n <= 1) return n == 0 ? 0 : nums[0];
int[] memo = new int[n];
memo[0] = nums[0];
memo[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++)
memo[i] = Math.max(memo[i - 1], nums[i] + memo[i - 2]);
return memo[n - 1];
}
}
0-1背包问题
416. 分割等和子集
难度中等214 收藏 分享 切换为英文 关注 反馈
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
把问题抽象为：
是否存在集合S的一个子集X，使得SUM(X)=SUM(S)/2?
S大小N不大于200，因此搜索+剪枝是完全可以AC的（偷懒没往DP上想hhhhhhhh）
策略：
对于S中的每一个元素，对于子集X，都有接受和丢弃两种操作，且这两种操作是互补且等价的
（可以想象有两个子集，接受是放到第一个子集中，丢弃是放到第二个子集里）。
1、当任意一个子集装满SUM(S)/2后，即成功找到一个解。
2、当任意一个子集超过SUM(S)/2后，则在此种分支下不可能找到一个可行解，剪枝。
class Solution {
public boolean canPartition(int[] nums) {
//涉及到剪枝的问题，先排个序
Arrays.sort(nums);
int sum = 0;
//算出SUM(S)
for (int n : nums){
sum += n;
}
//奇数肯定不行
if ((sum & 1) == 1){
return false;
}
sum >>= 1;
//搜索
return canPartition(nums, nums.length-1, sum, sum);
}
//DFS idx为当前元素，had为待接受上限，pass为待丢弃上限
private boolean canPartition(int[] nums, int idx, int had, int pass){
//找到可行解
if (had == 0 || pass == 0){
return true;
}
//剪枝
else if (had < 0 || pass < 0){
return false;
}
//继续搜索
else{
return canPartition(nums, idx-1, had-nums[idx], pass) || canPartition(nums, idx-1, had, pass-nums[idx]);
}
}
}
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。</pre>
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length==0)
return 0;
//a[i]表示以nums[i]结尾的最长子序列的长度
int [] a=new int [nums.length];
Arrays.fill(a,1);
for(int i=1;i<nums.length;i++)
for(int j=0;j<i;j++)
if(nums[j]<nums[i])
a[i]=Math.max(a[i],1+a[j]);
int res=1;
for(int i=0;i<nums.length;i++)
res=Math.max(res,a[i]);
return res;
}
}
