专题10：动态规划
题目509：斐波那契数（NO）
- 解题思路：动态五部曲
动态五部曲：这里我们用一个一维数组来保存递归的结果
-
确定dp数组以及下标的含义
dp[i]的定义为：第i个数的斐波那契数值是dp[i] -
确定递推公式
这道题已经把递推公式直接给了：状体转移方程dp[i]=dp[i-1]+dp[i-2]; -
dp数组如何初始化
这题题目把如何初始化也直接给了
dp[0]=0;
dp[1]=1; -
确定遍历顺序
从递归公式**dp[i]=dp[i-1]+dp[i-2]**中可以看出，dp[i]是依赖dp[i-1]和dp[i-2],那么遍历顺序一定是从前到后遍历的。 -
列举推导dp数组
按照这个递推公式dp[i]=dp[i-1]+dp[i-2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：0 1 1 2 3 5 8 13 21 34 55
如果代码写出来发现结果不对，就把dp数组打印出来看看和我们推导的数列是否一致的。
- 题目
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
class Solution {
public:
int fib(int n) {
if(n<=1)
{
return n;
}
vector<int>dp(n+1);
dp[0]=0;
dp[1]=1;
//这里实际的个数会是n+1
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
题目70：爬楼梯（NO）
- 解题思路：依旧是动规5步曲。
- 确定dp数组以及下标的含义
dp[i]：表示爬到第i层楼梯，有dp[i]种方法
这里来推导一下：dp[1]=1,dp[2]=2;dp[3]=3；dp[4]=5;这样递推又会得到和上题一样的答案
- 确定递推公式
dp[i]=dp[i-1]+dp[i-2]
- dp数组如何初始化
因为dp[0]是没有任何意义的，所以不用对其进行初始化，只需要知道dp[1]=1;dp[2]=2就可以了
- 确定遍历顺序
从递推公式dp[i]=dp[i-1]+dp[i-2]可以看出，遍历顺序一定是从前往后遍历的
- 列举dp数组
上面列举过了。
class Solution {
public:
int climbStairs(int n) {
if(n<=1) return n;
vector<int>dp(n+1);
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
- 疑惑点：为什么可以用dp[i]=dp[i-1]+dp[i-2]作为到达i层的方法数呢
具体解释如下：
- 到达第 i 层楼梯的最后一步： 想要到达第 i 层楼梯，最后一步只有两种可能：
- 从第 i-1 层爬一步。
- 从第 i-2 层爬两步。
- 方法数的累加：
- 从第 i-1 层爬一步，方法数为 dp[i-1]，因为到达第 i-1 层有 dp[i-1] 种方法。
- 从第 i-2 层爬两步，方法数为 dp[i-2]，因为到达第 i-2 层有 dp[i-2] 种方法。
- 总方法数： 由于最后一步只有这两种可能，所以到达第 i 层楼梯的总方法数就是这两种情况的方法数之和，即 dp[i] = dp[i-1] + dp[i-2]。
简单来说，dp[i] 就是把所有到达第 i 层楼梯的最后一步可能情况的方法数加起来。
举个例子：
假设我们要爬到第 4 层楼梯。
- 到达第 4 层的最后一步可以是：
- 从第 3 层爬一步，方法数为 dp[3]。
- 从第 2 层爬两步，方法数为 dp[2]。
- 因此，到达第 4 层的总方法数为 dp[4] = dp[3] + dp[2]。
总结：
dp[i] = dp[i-1] + dp[i-2] 这个公式体现了爬楼梯问题的递推关系，它将到达第 i 层楼梯的方法数分解为两种最后一步可能情况的方法数之和，从而简化了问题的求解过程。
题目746：使用最小花费爬楼梯（YES）
- 解题思路：动规5步曲
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
-
确定dp数组的含义
这里的dp[i]表示到达第i层所需要的最少的花费。 -
确定递推公式
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); -
如何初始化dp数组
根据题目就可以知道dp[0]=0 ,dp[1]=0; -
确定遍历的顺序
这里毫无疑问必然是从前往后，因为dp[i]需要用前面的两个数才能确定。 -
列举出dp数组
这里的本质意义是方便调试，但是这里比较动态，不好推导，不用列举也行。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
/*
这题依旧是动规5步曲：
1.确定dp数组的含义
dp[i]表示到达第i层最低的开销
2.确定递推公式
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3.dp数组如何初始化
dp[0]=0 dp[1]=0; 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
这句话表示不需要花费
*/
int n=cost.size();
vector<int>dp(n+1);
if(n<=1)
{
return 0;
}
dp[0]=0;
dp[1]=0;
for(int i=2;i<=n;i++)
{
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};
题目392：判断子序列（YES）
- 解题思路：这题就是要判断s再t中顺序的出现过了，所以只要对t进行一次for只要出现了s的元素s的指针就前进比较下一个。
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
class Solution {
public:
bool isSubsequence(string s, string t) {
int count=0;
if(s=="")
{
return true;
}else if(t=="")
{
return false;
}
for(int i=0;i<t.size();i++)
{
if(s[count]==t[i])
{
count++;
}
if(count>=s.size())
{
return true;
}
}
return false;
}
};
专题11：贪心算法
题目680：验证回文串||（NO）
- 解题思路：这题的解题思路是再普通验证回文数的方法上进行叠加的，如果left和right不相等就判断左边去掉一位（left++）或者右边去掉一个（right–）后的字符是否是回文数。这个是回文数的特性。
给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
class Solution {
public:
//自己封装一个接口用来判断是否是回文字符串
bool isPalindrome(string s,int left,int right)
{
int len=s.size();
if(len==0) false;
if(len==1) true;
while(left<right)
{
if(s[left]!=s[right])
{
return false;
}
left++;
right--;
}
return true;
}
bool validPalindrome(string s) {
int left = 0, right = s.size() - 1;
while (left < right) {
char c1 = s[left], c2 = s[right];
if (c1 == c2) {
++left;
--right;
} else {
return isPalindrome(s, left, right - 1) || isPalindrome(s, left + 1, right);
}
}
return true;
}
};
题目860：柠檬水找零（NO）
- 解题思路：这题一上来想到的就是哈希表，因为能开苏查找是否有钱，当是给5元时，直接收钱就行，当给10元时，需要退5元，当要给20时，退15，而这15有两种分配方法，10+5和5+5+5。分别看这些情况能否满足要求即可。
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
//使用哈希表来存钱
unordered_map<int,int>map;
for(int i=0;i<bills.size();i++)
{
switch(bills[i])
{
case 5:
//直接收钱
map[5]++;
break;
case 10:
//需要找5元，查找是否有5元
if(map[5])
{
//有
map[5]--;
map[10]++;
}else
{
return false;
}
break;
case 20:
//需要找15元
//情况1：10+5
if(map[10]&&map[5])
{
map[10]--;
map[5]--;
map[20]++;
}else if(map[5]>=3)
{
map[5]-=3;
map[20]++;
}else
{
return false;
}
break;
}
}
return true;
}
};
题目942：增减字符串匹配（NO）
- 解题思路：I就放剩余数字中的最小数，D就放剩余数字中的最大数。（这个其实也不好想）
由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
如果 perm[i] < perm[i + 1] ，那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ，那么 s[i] == ‘D’
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
- 官方题解
class Solution {
public:
vector<int> diStringMatch(string s) {
int n = s.length(), lo = 0, hi = n;
vector<int> perm(n + 1);
for (int i = 0; i < n; ++i) {
perm[i] = s[i] == 'I' ? lo++ : hi--;
}
perm[n] = lo; // 最后剩下一个数，此时 lo == hi
return perm;
}
};
题目1005：K次取反后最大化的数组和（YES）
- 解题思路：这个k表示又这么多的负号，这些符号应该优先将负数变为正数，后面如果k不为0则拿最小的正数来处理这个k。
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
- myself(这个代码我调试的时候打了一下调试信息)
class Solution {
public:
//冒泡排序
void bubble_sort(vector<int>&nums)
{
int len=nums.size();
for(int i=0;i<len-1;i++)
{
for(int j=0;j<len-i-1;j++)
{
if(nums[j]>nums[j+1])
{
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
//这个k实际就是又多少个负号，
//先进行排序
bubble_sort(nums);
int sum=0;//统计最大值
int current_min=INT_MAX;//记录正数的最小值
int current_min_index=0;//记录最小值的下表
for(int i=0;i<nums.size();i++)
{
//这次遍历先处理数据
//将所有的负数变成正数
if(nums[i]<0&&k>0)
{
nums[i]=abs(nums[i]);
k--;
}
//统计最小值
if(current_min>nums[i])
{
current_min=nums[i];
current_min_index=i;
}
}
for(int i=0;i<nums.size();i++)
{
std::cout<<nums[i]<<" ";
}
std::cout<<std::endl;
std::cout<<"k="<<k<<std::endl;
std::cout<<"min="<<current_min<<std::endl;
//上面这次遍历又两种情况
//一种是k==0那这种就直接加就行
//另一种是k!=0说明现在nums全部都是正数，则拿一个最小正数来处理这个就行
int ans=0;
if(k==0)
{
for(int i=0;i<nums.size();i++)
{
ans+=nums[i];
}
}else
{
for(int i=0;i<nums.size();i++)
{
if(i==current_min_index)
{
//用这个来处理剩下的k
if(k%2==1)
{
nums[i]=(-nums[i]);
}
}
ans+=nums[i];
}
}
return ans;
}
};