70.爬楼梯
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
题解
爬楼梯，找到传递函数。
dp[i]=dp[i-1]+dp[i-2]。
dp[1]=1,dp[2]=2.
class Solution { public: int climbStairs(int n) { if(n==1) return 1; int a=1,b=1; int sum=a+b; for(int i=2;i<=n;i++){ sum=a+b; a=b; b=sum; } return sum; } };
198.打家劫舍
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
题解不能偷相邻的房间，求最大收获
dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
定义一个数组 dp ， dp[i] 表示抢劫到第 i 个房子时，可以抢劫的最大数量。我们考虑 dp[i]， 此时可以抢劫的最大数量有两种可能，一种是我们选择不抢劫这个房子，此时累计的金额即为dp[i-1]；另一种是我们选择抢劫这个房子，那么此前累计的最大金额只能是 dp[i-2] ，因为我们不能够抢劫第 i-1 个房子，否则会触发警报机关。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0)
return 0;
int n=nums.size();
vector<int> dp(n+1,0);
dp[1]=nums[0];
for(int i=2;i<=n;i++){
dp[i]=max(dp[i-1],nums[i-1]+dp[i-2]);
}
return dp[n];
}
};413.等差数列的划分
题目
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
- 例如，
[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。给你一个整数数组
nums，返回数组nums中所有为等差数组的 子数组 个数。子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4] 输出：3 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。示例 2：
输入：nums = [1] 输出：0提示：
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000
题解
等差数列，那就是nums[i]-nums[i-1]=nums[i-1]-nums[i-2]，证明nums[i]与前面的两个数可以构成等差数列。如果满足前面条件，dp[i]=dp[i-1]+1。
最后求dp数组的和。
class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { // nums[i]-nums[i-1]=nums[i-1]-nums[i-2] if(nums.size()<3) return 0; int n=nums.size(); int sum=0; vector<int> dp(n,0); for(int i=2;i<n;i++){ if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){ dp[i]=dp[i-1]+1; sum+=dp[i]; } } return sum; } };
