蓝桥动态规划（dp）题目讲解
前言：动态规划（dp）一直都是蓝桥杯等算法比赛常常要考的知识点，借助这个机会，我把我的一些看法（比较初级）分享给大家。
dp的题比较重要的就是定义，初始化和状态转移方程。我们直接上例子。
LeetCode-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 阶
提示：
1 <= n <= 45
思路：
题目说每次可以爬 1 或 2 个台阶。我们就可以知道第i阶可以由第i-1阶爬1楼到达，也可以由第i-2阶爬2楼到达。 这里我们定义dp[i]为到达第i阶的方案数。 所以可以得到状态转移方程dp[i]=(dp[i-1]+dp[i-2])。初始化：dp[1]=1,dp[2]=2。也就是第1阶肯定是由第0阶爬1阶到的，第2阶可以爬2次1阶和1次2阶到达，也就是2种方法。 感觉和斐波拉契数列有点类似。
代码：
class Solution {
public:
int climbStairs(int n) {
int dp[50]={0};//dp[i]表示第i阶有几种方法
if(n==1) return 1;
if(n==2) return 2;
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-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
思路：
这里我就简单讲了。如果只有2间屋子，要么一间偷，一间不偷，偷的话，肯定是偷钱多的（小偷也聪明）。如果屋子多的话，就需要比较了，偷第i间，那么i-1间不能偷，偷的钱就是第i间加上前面i-2间偷的。 如果不偷第i间，那么就是前i-1间偷的和。 初始化：dp[0]=nums[0];dp[1]=max(nums[0],nums[1])。 状态转移方程：dp[i]=max(dp[i-1],dp[i-2]+nums[i])
代码：
class Solution {
public:
int rob(vector<int>& nums) {
int dp[105]={0};
int n=nums.size();
if(n==1) return nums[0];
dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);
for(int i=2;i<n;i++)
{
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);//每个屋子要么偷，要么不偷
}
return dp[n-1];
}
};下面再贴1道题，大家自己思考。
牛客周赛 Round 72-小红的01串（四）
题目描述
小红拿到了一个01串，她初始站在第一个字符。小红可以进行以下移动方式：
1. 花费x能量，移动到当前位置右边、离当前位置最近的，和当前字符相同的字符；
2. 花费y能量，移动到当前位置右边、离当前位置最近的，和当前字符不同的字符。
小红想知道，她移动到最右端的最小花费是多少？
输入描述:
第一行输入三个正整数n,x,y，用空格隔开，代表01串长度、第一种移动花费，第二种移动花费。 第二行输入一个长度为n的01串。 1≤n,x,y≤1e5
输出描述:
一个整数，代表花费的最小总能量。
输入
5 1 2 01011
输出
4
说明
有两种方案均可：操作2+操作1+操作1 或者 操作1+操作2+操作1。
代码：
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
int main()
{
ll n, x, y;
cin >> n >> x >> y;
string s;
cin >> s;
vector<ll> dp(n, 1e18);
dp[n - 1] = 0;
ll next0 = -1, next1 = -1;
for (ll i = n - 1; i >= 0; i--)
{
if (s[i] == '0')
{
if (next0 != -1)
{
dp[i] = min(dp[i], dp[next0] + x);
}
if (next1 != -1)
{
dp[i] = min(dp[i], dp[next1] + y);
}
next0 = i;
}
else
{
if (next1 != -1)
{
dp[i] = min(dp[i], dp[next1] + x);
}
if (next0 != -1)
{
dp[i] = min(dp[i], dp[next0] + y);
}
next1 = i;
}
}
cout << dp[0] << endl;
return 0;
}谢谢大家的观看，本人算法小白，有不足和错误请大家指出，比较难的dp在这就不阐述了（不会）！大家天天开心！
原文地址：https://blog.csdn.net/2301_80079117/article/details/145289196
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！