`
- 浏览:
240202 次
- 性别:
- 来自:
北京
-
动态规划算法两要素
•递归方程式(状态转移方程式)
•保存子问题的解
无穷数列1,1,2,3,5,8,13,21,34,55,…,称为Fibonacci数列。它可以递归地定义为
1 n = 0
F(n) = 1 n = 1
F(n – 2) + F(n – 1) n > 1
保存子问题的解
#define MAX 1000
__int64 temp[MAX] = {0};
__int64 fibonacci(int n)
{
int i = 0;
temp[0] = 1;
temp[1] = 1;
for(i=2; i<= n; i++)
{
temp[i] = temp[i-1] + temp[i-2];
}
return temp[n];
}
基本思想:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解(多阶段决策);
对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解 (填表)。
动态规划算法步骤
(1)找出最优解的性质,并刻画其结构特征。
(2)递归地定义最优值
(3)以自底向上的方式计算出最优值
(4)根据计算最优值时得到的信息,构造一个最优解
例子1:最大子段和
最大字段和问题,即给定n个整数(可能有0和负数)组成的序列a1 a2 a3.......an, 求其最大连续子段和。如有(-2, 11, -4, 13, -5, -2),则最大子段和 11-4+13=20。
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define N 14
int MaxSumDP(int *a, int n); //动态规划法
int a[N] = {9, -7, 3,-1, 4, 5, -10, -2, 9, 1, -3, -4, 6, 2};
int b[N];//b[i]表示以a[i]为最后一个元素的最大子段和
int main()
{
printf("The MaxSubSum using DP: %d\n", MaxSumDP(a, N));
getchar();
return 0;
}
int MaxSumDP(int *a, int n) //动态规划法
{
int i, maxSum = 0;
if(a[0] > 0)
maxSum=b[0]=a[0];
for(i=1; i<n; ++i)
{
b[i] = (b[i-1]+a[i] > 0) ? (b[i-1]+a[i]) : 0;//记录每个子结构的和,如果前面的i-1
if(maxSum < b[i]) //已经是小于0,后面的直接赋值就a[i]
maxSum = b[i];
}
return maxSum;
}
可以看出动态规划法的复杂度只有O(n),但需要O(n)的空间,而分治法的复杂度是O(nlogn),可见动态规划法更优秀。在动态规划法中,b[n]数组的元素b[i]代表的意思是:
如果a[0]=0,则b[0]=a[0],否则b[0]=0,然后对于b[i]
b[i] = MAX( b[i -1] + a[i], 0 );
即b[i]等于b[i-1]+a[i] 和 0 中的较大者
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
动态规划解最大自序列和经典DP算法 最大连续子序列
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
1. 将矩阵的某一行看成一个序列,设计算法求该序列的最大子序列。 2. 将矩阵相邻两行对应列的元素相加形成一个新的序列,试分析该子序列中每-一个元素的含义,其最大子序列的含义。 3. 设计算法求解该问题,分析样例...
动态规划——最大连续子序列和一维最大连续子序列和[x] LeetCode 53 Maximum Subarray设$d[i]$表示以序列中$s[i]$结尾的最大
1. 掌握动态规划法的设计思想并能熟练运用 2. 强化动手编程的能力 二. 实验内容 用动态规划法求两个序列的最大公共子序列 三. 算法思想 1. 分析可得如下动态规划函数: ① L[0][0]=L[i][0]=L...
用动态规划求最长公共子序列: 问题:求给定两个序列的最长公共子序列,要求输入两个序列,输出它们的最长公共子序列及其长度值。
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
编程实现最大子段和问题的求解(分别采用分治法和动态规划法求解) 编程实现最长公共子序列(LCS)问题的求解 设计算法求解数字三角形问题,并编程实现。(P90算法实现题3-7)
求最长公共子序列问题的一种快速算法,刘佳梅,,本文主要描述一种不同于动态规划法的一种新的求解最长公共子序列问题的方法,该算法主要是把求解公共字符串问题转化为求解矩阵L(p,m
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
里面主要有关于线性问题中最长公共子序列,最长递增递减子序列,最大子段和,需不需要输出位置,还有最长公共递增子序列,当然,最重要的是可以直接用
最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...
采用java语言实现了寻找最大子序列的算法, 主要用到了动态规划的思想。
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
求最大字段的三种方法——_动态规划_蛮力_分治算法
这个源代码描述的是给定两个字符串,根据动态规划算法来计算出这两个字符串的最大子字符串。
字符串相关的动态规划最大公共子序列最大公共子串编辑距离 简述这三个算法解决的问题和展示状态转移方程并且给出可通过执行的Python代码。 最大公共子序列 子序列是,一个字符串中的任意字符组成的序列,重点在于,...