Leetcode算法刷题笔记7-动态规划

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode算法刷题笔记7-动态规划，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4678字，纯文字阅读大概需要7分钟。

内容图文

Leetcode算法刷题笔记7-动态规划

• Leetcode 70. 爬楼梯
• • 方法壹 暴力回溯
  • 方法贰 动态规划
  • 方法叁 动态规划+优化
• Leetcode 53. 最大子序和
• • 方法壹 动态规划
  • 方法贰 动态规划+优化
• Leetcode 198. 打家劫舍
• 尾语

相关刷题笔记博客
Leetcode算法刷题笔记1-链表
Leetcode算法刷题笔记2-栈、队、堆
Leetcode算法刷题笔记3-递归与回溯
Leetcode算法刷题笔记4-贪心
Leetcode算法刷题笔记5-二叉树
Leetcode算法刷题笔记6-图

Leetcode 70. 爬楼梯

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

方法壹 暴力回溯

#include<bits/stdc++.h>
using namespace std;
//Leetcode提交部分 
class Solution {
public:
    int climbStairs(int n) {
        if(n==1||n==2){
        	return n;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
};
//Leetcode自行使用编译器（如DEV\VC\VS）测试部分 
int main(){
	int n;//自己输入有多少台阶 
	cin>>n;
	Solution solve;
	cout<<solve.climbStairs(n)<<endl;
	return 0;
}

方法贰 动态规划

#include<bits/stdc++.h>
using namespace std;
//Leetcode提交部分 
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+3,0);
        dp[1]=1;
        dp[2]=2;
        for(int i =3;i<=n;i++){
        	dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};
//Leetcode自行使用编译器（如DEV\VC\VS）测试部分 
int main(){
	int n;//自己输入有多少台阶 
	cin>>n;
	Solution solve;
	cout<<solve.climbStairs(n)<<endl;
	return 0;
}

方法叁 动态规划+优化

#include<bits/stdc++.h>
using namespace std;
//Leetcode提交部分 
class Solution {
public:
    int climbStairs(int n) {
        int l=0,m=0,r=1;
        for(int i=0;i<n;i++){
            l = m;
            m = r;
            r = m+l;

        }
        return r;
    }
};
//Leetcode自行使用编译器（如DEV\VC\VS）测试部分 
int main(){
	int n;//自己输入有多少台阶 
	cin>>n;
	Solution solve;
	cout<<solve.climbStairs(n)<<endl;
	return 0;
}

Leetcode 53. 最大子序和

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

方法壹 动态规划

#include<bits/stdc++.h>
using namespace std;
//Leetcode提交部分 
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        if(nums.size()==1){
            return nums[0];
        }
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        int maxres = dp[0];
        for(int i=1;i<nums.size();i++){
            dp[i] = max(nums[i],dp[i-1]+nums[i]);
            if(maxres<dp[i]){
                maxres = dp[i];
            }
        }
        return maxres;
    }
};
//Leetcode自行使用编译器（如DEV\VC\VS）测试部分 
int main(){
	int n[9] = {-2,1,-3,4,-1,2,1,-5,4};//自己输入有多少台阶 
	vector<int> nums;
	for(int i=0;i<9;i++){
		nums.push_back(n[i]);
	}
	Solution solve;
	cout<<solve.maxSubArray(nums)<<endl;
	return 0;
}

方法贰 动态规划+优化

#include<bits/stdc++.h>
using namespace std;
//Leetcode提交部分 
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};
//Leetcode自行使用编译器（如DEV\VC\VS）测试部分 
int main(){
	int n[9] = {-2,1,-3,4,-1,2,1,-5,4};//自己输入有多少台阶 
	vector<int> nums;
	for(int i=0;i<9;i++){
		nums.push_back(n[i]);
	}
	Solution solve;
	cout<<solve.maxSubArray(nums)<<endl;
	return 0;
}

Leetcode 198. 打家劫舍

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber/

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 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 。

#include<bits/stdc++.h>
using namespace std;
//Leetcode提交部分 
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        if(nums.size()==1){
            return nums[0];
        }
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        dp[1] = max(dp[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
};
//Leetcode自行使用编译器（如DEV\VC\VS）测试部分 
int main(){
	int n[6] = {5,2,6,3,1,7};//自己输入有多少台阶 
	vector<int> nums;
	for(int i=0;i<6;i++){
		nums.push_back(n[i]);
	}
	Solution solve;
	cout<<solve.rob(nums)<<endl;
	return 0;
}

尾语

诚邀各校各地有志之士加入我们大学生IT学习群交流：871352155（请各位广告大佬高抬贵手，常讨论学习无关的朋友请出门右拐∑(っ°Д°;)っ）

内容总结

以上是互联网集市为您收集整理的Leetcode算法刷题笔记7-动态规划全部内容，希望文章能够帮你解决Leetcode算法刷题笔记7-动态规划所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---