动态规划
爬*
题目描述
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
思路
爬楼梯每次只能跨一步或者两边，需要你来求解爬n层楼梯所有有可能的走法。
如果一共有十层楼梯。现在你只差最后一步到第十层楼梯。那么有哪几种情况呢？
当然就是两种。一个是从第九级走一步到第十级。一个是从第八级跨两层到第十级。
那么如果，走到第九层的走法有x种，走到第八层的走法有y种。那么走到第十层的走法有多少种呢？？
答案自然是x+y种。
我们将这种解法进行推广。求解到n层台阶一共有多少种走法。
因此如果我们设f(n)表示为到n层楼梯的走法，则有
f(n)=f(n-1)+f(n-2)成立。
找到了这样一个递推的关系式。我们如何来求解呢？
递归求解
递归求解是能够想到的最自然的一种方式。
class Solution {
public:
int climbStairs(int n) {
if(n==0)return 0;
if(n==1)return 1;
if(n==2)return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
};
时间复杂度达到了O(2^n),在letcode中会显示超时。
备忘录算法（记忆化搜索）
我们不难发现如果用简单的递归来完成。有的项会被重复的计算。算f(10)时，需要算f(9)和f(8)。算f(9)时会计算f(8)和f(7)。以此类推，会发现做了很多重复的工作。那么如何去避免呢？
一种方案就是，我们把已经算过的值保存下来。下次如果再遇到，我们就不用再重复计算了。这叫备忘录算法，也就是我们熟知的记忆性搜索。代码如下
class Solution {
public:
map<int,int>has;
int climbStairs(int n) {
if(has[n]) return has[n];
if(n==0)return 0;
if(n==1)return 1;
if(n==2)return 2;
has[n] = climbStairs(n-1)+climbStairs(n-2);
return has[n];
}
};
这样一来程序的性能得到了很大的提高。时间复杂度和空间复杂度都是O(N)。
动态规划
在之前的求解中，都是自上而下的求解，也就是递归的思想。不妨我们换一下思路，自下而上去解决这个题目。
台阶数 1 2 3 4 5 6 7 8 9 10
走法 1 2 3 5 8 13 21
有f(1)和f(2)推出f(3)
由f(2)和f(3)推出f(4)
再有f(4)和f(5)去推出f(6)
以此类推，我们就可以自底向上去推出f(n)的结果了
class Solution {
public:
int climbStairs(int n) {
int a[n+2];
a[1] = 1;
a[2] = 2;
for(int i=3;i<=n;i++){
a[i] = a[i-1]+a[i-2];
}
return a[n];
}
};
其实细细看来，依然有需要提高的地方。其实当计算a[i]是我们只需要a[i-1]和a[i-2]。也就是只需要两个变量来保存结果即可。因此，可以得到以下的代码
class Solution {
public:
map<int,int>has;
int climbStairs(int n) {
if(n==0)return 0;
if(n==1)return 1;
if(n==2)return 2;
int a=1;
int b=2;
for(int i=3;i<=n;i++){
int tmp = b;
b = a + b;
a = tmp;
}
return b;
}
};
买卖股票的最佳时机
题目描述
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
思路
要求用动态规划来求解。那么最关键的就是找到状态转移方程。
f(n)表示n天买卖股票能够获得的最大利润。很显然只有两种情况
第一是今天把股票卖出去了。能够获得的最大利润就是第n天股票的价格减去前n-1天股票的最低价
第二是今天没有卖股票。买卖股票能够获得的最大利润保持不变，也就是和n-1天的一样
那么第n天能够获得的最大价值就是这两种情况中的最大值了。、
这样我们就可以推出状态转移方程a[i] = max(a[i-1],prices[i]-minprice)
边界条件自然是n=1时。代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n==0) return 0;
int a[n+2];
a[0] = 0;
int minprice=prices[0];//记录最低价格
for(int i=1;i<n;i++){
a[i] = max(a[i-1],prices[i]-minprice);
if(prices[i]<minprice){
minprice = prices[i];
}
}
return a[n-1];
}
};
最大子序和
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
思路
最简单粗暴而又一定超时的方法就是暴力枚举。这里就不说了。
但是值得一提的是，在枚举的过程中，是把所有位置的元素作为子序列开头的情况进行了枚举。
这里，我们换一个思路。去找所有以第n个数为结束点的子序列。
并用f(n)表示以第n个数为结尾的子序列的最大值。
以n为结尾的子序列有两种可能。
一是第n个数，与以第n-1个数为结束的子序列相连接，形成新的子序列
二是以第n个数，这单独一个数作为子序列。
这两种情况的最大值，也就是f(n)的值。
遍历求得所有的f(n)，再找出f(n)中的最大值，也就是题目的最终答案了。
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//f（n）表示以第n个数为结束点的子序列的最大和
// 有递推关系f(n)=max(f(n-1)+a[n],a[n])
// 找出这些中最大的那个
int n = nums.size();
if(n==0) return 0;
int ans = nums[0];
int f[n+1];
f[0] = nums[0];
for(int i=1;i<n;i++){
f[i] = max(f[i-1]+nums[i],nums[i]);
ans = max(ans,f[i]);//更新最大值
}
return ans;
}
};
打家劫舍
题目描述
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
思路
考虑所有可能的抢劫方案过于困难。一个自然而然的想法是首先从最简单的情况开始。记：
f(k) = 从前 k 个房屋中能抢劫到的最大数额，nums[i]= 第 i 个房屋的钱数。
首先看 n = 1 的情况，显然 f(1) = nums[0]
再看 n = 2，f(2) = max(num[0],num[1])
对于 n = 3，有两个选项:
抢第三个房子，将数额与第一个房子相加。
不抢第三个房子，保持现有最大数额。
显然，你想选择数额更大的选项。于是，可以总结出公式：ans[i] = max(ans[i-2]+nums[i],ans[i-1])
class Solution {
public:
int rob(vector<int>& nums) {
// f(n)表示前n家店打劫的最大金钱。
//f(n) = max(f(n-2)+a[n],f(n-1)).
int n = nums.size();
if(n==0) return 0;
if(n==1) return nums[0];
int ans[n];
ans[0] = nums[0];
ans[1] = max(nums[0],nums[1]);
for(int i=2;i<n;i++){
ans[i] = max(ans[i-2]+nums[i],ans[i-1]);
}
return ans[n-1];
}
};
其实只要记录前两个的值就