动态规划 经典问题

今天记录下自己所学的动态规划知识点

题目1：

有三枚硬币 2,5,7 拼成27元

最少需要几枚硬币

我自己理解的动态规划实操两部曲

第一曲：定义初始条件

第二曲：循环操作 以及状态方程定义

/**
我的第一个动态规划程序 

题目信息：
有三枚硬币  2,5,7  拼成27元
最少需要几枚硬币

看到最少：一般用动态规划求解 

1.初始条件：f[0]=0;
2.转移方程  f[27]=min{f[27-2]+1,f[27-5]+1,f[27-7]+1} 

*/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
	
	int f[100];//第一步 开辟数组 
	
	f[0]=0;//第二步 初始条件
	 
	int i;
	int m;
	
	int coins[3]={2,5,7};
	for(i=1;i<=27;i++){//第三步 for循环 
		
		f[i]=9999;
		
		for(int j=0;j<3;j++){
			
			if(i>=coins[j]&&f[i-coins[j]]<9999)//判断条件 
			f[i]=min(f[i],f[i-coins[j]]+1);
		}
	}
	
		printf("%d\n",f[i-1]);
}
           

题目2：

给的m行n列的网络，有一个机器人从左上角(0,0)出发，每一步

可以向下或者向右走一步，问有多少种不同的方式可以走到右下角

/**

题目：
给定m行n列的网络，有一个机器人从左上角(0,0)出发，每一步
可以向下或者向右走一步，问有多少种不同的方式可以走到右下角 

*/ 
#include <stdio.h>
int  main(){
	
	int m,n;
	
	int f[m][n];//开辟数组 
	
	
	int i,j;
	for(i=0;i<m;i++){
		
		for(j=0;j<n;j++)
		
		if(i==0||j==0)
			f[i][j]=1;//初始状态  第0行 第0列 只有一种方式 
		
		else {
			
			f[i][j]=f[i-1][j]+f[i][j-1];//转移方程 
		}
		
	}
	printf("%d",f[m-1][n-1]);
	return 0;
}

           

动态规划小结：

1.确定状态

2.转移方程

3.初始条件和边界情况

4.计算顺序

题目3：

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

/**

乘积最大子序列
2,3,-2,4
乘积最大为6

-2,0,1
乘积最大为0 

思路：
设置两个值 maxp,minp
因为maxp*number[i]  可能成为最小值
    minp*number[i]  可能成为最大值 

初始条件


边界值

转移方程 

maxp[i+1]=max(maxp[i]*number[i+1],minp[i]*number[i+1],number[i+1])

minp[i+1]=min(minp[i]*number[i+1],maxp[i]*number[i+1],number[i+1])


dp[i + 1] = max(dp[i], maxp[i + 1])
*/
#include <cstdio>

#include <iostream>
#include <algorithm>
using namespace std;
int  mul(int number[],int n){

	
	if(numSize==1)
		return number[0];
		
	int p=nums[0];//初始条件 
	int maxp=nums[0];
	int minp=nums[0];
	
	for(int i=1;i<numSize;i++){
		
		int t=maxp;
		
		maxp=max(max(nums[i],maxp*nums[i]),minp*nums[i]);//转移方程 
		
		minp=min(min(nums[i],minp*nums[i]),t*nums[i]);
		
		p=max(p,maxp);
	}
	
	return p;
	
}

int main(){
	
	
	int number[5]={2,3,-2,4,0};
	
	int max=mul(number,5);
	
	printf("%d\n",max);
	return 0;
}
           

题目4：连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1：

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

AC代码：

/**

连续子数组的最大和


输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

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


解决方案：
 

*/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int max_function(int number[],int l){
	
	if(l==1)
		return nums[0];
		
	int i;
	
	int p=nums[0];//初始化 
	int maxp=nums[0];
	for(i=1;i<l;i++){
		
		
		maxp=max(maxp+nums[i],nums[i]);//转移方程 
		
		p=max(p,maxp);
		
	}
	return p;
	
}
int main(){
	
	int number[9]={-2,1,-3,4,-1,2,1,-5,4};
	
	int m=max_function(number,9);
	
	printf("%d\n",m);
	
	return 0;
}