问题1.钞票支付问题。
有1元、2元、5元、10元、20元、50元、100元的钞票无穷多张。现使用这些钞票支付x元，最少需要多少张？例如，X=628最佳支付方法：6张100块的，1张20块的，1张5块的，1张2块的，1张1块的；共需要6+1+1+1+1=10张。直觉告诉我们：尽可能多的使用面值较大的钞票！贪心法：遵循某种规律，不断贪心的选取当前最优策略的算法设计方法。
为何这么做一定是对的？面额为1元、2元、5元、10元、20元、50元、100元，每个面额是比自己小的面额的2倍或以上。所以当使用一张较大面额钞票时，若用较小面额钞票替换，需要两张或更多的钞票！例如：2=1+15=2+2+110=5+520=10+1050=20+20+10100=50+50故，当前最优解即为全局最优解，贪心成立！思考：如果增加7元面额，贪心还成立吗？
如果有一张7块钱面额 贪心不成立使用动态规划
需要面额为1的1张，剩余需要支付RMB0。
#include <stdio.h>
总北需要10张RMB int main（）{//人民币面额请按在意键继续…
const int RMB[]={100，50，20，10，5，2，1}；const int NUM=7；//7种面额int x=628；//用RMB最少多少张，组成X？
int count=0；for（inti=0；i<NUM；i++）{
int use=x/RMB[i]；//需要面额为RMB[i]的use张count+=use；//总计增加use张x=x-RMB[i]*use；//将总额减去使用RMB[i]已组成的金额printf（”需要面额为d的d张，”，RMB[i]，use）；printf（”剩余需要支付RMB 8d.\n”，x）；
}
printf（”总共需要sd张RMB\n”，count）；return 0；国国
}
k吻|日④105%·C|品圈图|高
leetcode 376
一个整数序列，如果两个相邻元素的差恰好正负（负正）交替出现，则该序列被称为
摇摆序列。一个小于2个元素的序列直接为摇摆序列。
例如：
序列[1，7，4，9，2，5]，相邻元素的差（6，-3，5，-7，3），该序列为摇摆序列。
序列[1，4，7，2，5]（3，3，-5，3）、[1，7，4，5，5]（6，-3，1，0）不是摇摆序列。
给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度。
例如：
输入[1，7，4，9，2，5]，结果为6；输入[1，17，5，10，13，15，10，5，16，8]，结果为7（[1，17，10，13，10，16，8]
）；输入[1，2，3，4，5，6，7，8，9]，结果为2。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()<2){
return nums.size();
}
static const int BEGIN = 0;
static const int UP = 1;
static const int DOWN = 2;
int STATE = BEGIN;
int max_length = 1;
for(int i = 1;i<nums.size();i++){
switch(STATE){
case BEGIN:
if(nums[i]>nums[i-1]){
STATE = UP;
max_length++;
}else if(nums[i]<nums[i-1]){
STATE = DOWN;
max_length++;
}
break;
case UP:
if(nums[i]>nums[i-1]){
STATE = UP;
}else if(nums[i]<nums[i-1]){
STATE = DOWN;
max_length++;
}
break;
case DOWN:
if(nums[i]>nums[i-1]){
STATE = UP;
max_length++;
}else if(nums[i]<nums[i-1]){
STATE = DOWN;
}
break;
}
}
return max_length;
}
};
leetcode 402
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
- num 的长度小于 10002 且 ≥ k。
- num 不会包含任何前导零。
class Solution {
public:
string removeKdigits(string num, int k) {
std::vector<int> s;
std::string result = "";
for(int i = 0;i<num.length();i++){
int number = num[i] - '0';
while(s.size()!=0 && s[s.size()-1]>number && k>0){
s.pop_back();
k--;
}
if(number!=0||s.size()!=0){
s.push_back(number);
}
}
while(s.size()!=0&& k>0){
s.pop_back();
k--;
}
for(int i = 0;i<s.size();i++){
result.append(1,'0'+s[i]);
}
if(result == ""){
result = "0";
}
return result;
}
};
