dp动态规划(硬币问题)（lis最长上升子序列问题）

定义：按照定义：动态规划是把一个大问题拆解成一堆小问题，且这些小问题可以重复利用至求出大问题。

即什么时候能用dp：
1满足最优子结构
  大问题的最优解可以由小问题的最优解推出，大问题与小问题求解思路一致。
2.满足无后效性
 一旦f（n）确定，后续就可直接调用它的值，而不用关心它是怎么样过来的。即可从小问题退出大问题。
3.设计好状态
 想办法把当前局面给表达出来 
4.设计好状态转移方程
  我从哪里来，或我到哪里去

问题：

若干硬币，面值 1，5，10，20，50，100
凑出价值w，至少需要多少硬币。比如w=600；
思路一（贪心策略）：每次面值最大思考：即一共需要 10枚
         6枚100，1枚50，1枚10，1枚5，一枚1 
        缺点:但是如果面值为1，5，11.凑15.用贪心则为5，实际只需要3枚5 （鼠目寸光，贪心的缺    点） 
思路二： 暴力枚举，但是复杂度太高，容易超时。
思路三（dp）：每次选取，更新剩余，整合之前最优在解决

dp思路：从凑出价值为0开始计算每部小问题最少需要多少硬币，进而退出更大的价值至少需要多少硬币。

分析：

从小问题逐渐求出大问题，且比较每部小问题最少需要多少个硬币。

#include
 using namespace std;
 int min(int a,int b){
 	return a=0)cost=min(cost,dp[i-1]+1);
 		if(i-5>=0) cost=min(cost,dp[i-5]+1);
 		if(i-11>=0)cost=min(cost,dp[i-11]+1);
 		dp[i]=cost; //不断更新。 
 		cout< 
 
lis（最长上升子序列问题） 
 
问题：给定长度为n的序列，从中选取一个子序列
 这个子序列需要单调递增，问最长上升子序列（lis）长度。 
 
 
 

思路：以每一个值为序列结尾，比较它前面比他小且递增的值，更新状态。最后比较哪一个值为序列结尾时最长。 即此时为最长上升最序列。
 考虑比x小的每一个p，若a[x]>a[p]即，f（x）=f(p)+1;
 
 
 
 
例：序列: 1 3 8 4 5  
 
  当1为最后一个时，可由本身  即f（1）=1；
 
  当3为最后一个时，可以由1推过来，即f(3)=f（1）+1=2
 
                                 或自己推自己：f(3)=0+1=1；     即为f(3)=2.
 
   当8为最后一个时，  可由1推   即f（8）=f（1）+1=2。
 
                                  可由3推过来，即f(8)=f（3）+1= 3.
 
                                  或自己推自己。  f(8)=0+1=1      即f（8）=3
 
  当4为最后一个时  即f（4）=f（1）+1=2  或  f（4）=f（3）+1=3 或f（4）=0+1=1  即f（4）=3
 
当5为最后一个时   f（5）=f（1）+1=2
 
                             f（5）=f（3）+1=3
 
                             f（5）=f（4）+1=4
 
                              f(5)=0+1=1.              即f（5）=4。
 
即max(f（1），f（3），f（8），f（4），f(5))=4
 
#include
using namespace std;
int a[100];
int dp[100];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++){
		dp[i]=1;//初始为1 
		for(int j=1;j 
 
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5713329.html