动态规划选讲1

简介

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。


LeetCode 5 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

示例 2:

分析:

设置dp[s,size()][s.size()]大小的dp布尔类型的数组,其中dp[i][j]代表字符串s从i到j是一个回文,递推存在以下几种情况:

  • 显然从自己到自己单个字符是 dp[i][i] = true
  • 当i******j中间的*部分是回文时如果s[i]==s[j]则i到j也是回文,如果中间的不是回文,则i到j也不是回文,及dp[i][j] = dp[i+1][j-1]
  • 如果s[i] == s[i - 1]则dp[i][i-1] = dp[i-1][i] = true

C++代码:


LeetCode 152 乘积最大子序列

给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

示例 1:

示例 2:

分析:
这个不同于LIS,因为是连续的,所以只需要判断相邻的即可。
另外乘积由于负负得正,因此需要保存两个值,当前最大值,当前最小值即可

C++代码:


LeetCode 279 完全平方数

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

示例 2:

分析:

此题即最少硬币问题:硬币对应于完全平方数。因此我们先计算好小于n的完全平方数,接下来通过动态规划数组dp[n]来计算,其中dp[i]代表正整数i最少组成个数。当当前完全平方数x小于整数i时,我们判断dp[i-x]+1与dp[i]的大小,如果dp[i-x]较小,则替换掉。另外dp[0]=0。

C++代码:

 

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注