简介
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
LeetCode 5 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
|
1 2 3 |
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 |
示例 2：
|
1 2 |
输入: "cbbd" 输出: "bb" |
分析：
设置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++代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: string longestPalindrome(string s){ if (s.size() < 2) return s; int dp[10000][10000] = {0}; int start = 0, len = 1; //start表示开始下标，len表示字串长度 for(int i = s.size() - 1; i >= 0; --i){ dp[i][i] = 1; if(i >= 1 && s[i] == s[i - 1])dp[i][i-1] = dp[i-1][i] = 1; for(int j = i + 1; j < s.size(); ++j){ if(s[i] == s[j]){ dp[i][j] = dp[i+1][j-1]; if(dp[i][j] && j - i + 1 > len){// 记录位置 start = i; len = j - i + 1; } } } } return s.substr(start, len); } }; |
LeetCode 152 乘积最大子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
|
1 2 |
输入: [2,3,-2,4] 输出: <code>6</code> 解释: 子数组 [2,3] 有最大乘积 6。 |
示例 2:
|
1 2 3 |
输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 |
分析：
这个不同于LIS，因为是连续的，所以只需要判断相邻的即可。
另外乘积由于负负得正，因此需要保存两个值，当前最大值，当前最小值即可
C++代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: int maxProduct(vector<int>& nums) { vector<int> posi(nums.size(), 0); vector<int> negt(nums.size(), 0); posi[0] = nums[0]; negt[0] = nums[0]; int ans = nums[0]; for(int i = 1; i < nums.size(); i++){ posi[i] = max(nums[i], max(nums[i] * posi[i-1], nums[i] * negt[i-1])); negt[i] = min(nums[i], min(nums[i] * posi[i-1], nums[i] * negt[i-1])); ans = max(posi[i], ans); } return ans; } }; |
LeetCode 279 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
|
1 |
输入: <em>n</em> = <code>12</code> 输出: 3 解释: <code>12 = 4 + 4 + 4. |
示例 2:
|
1 |
输入: <em>n</em> = <code>13</code> 输出: 2 解释: <code>13 = 4 + 9. |
分析：
此题即最少硬币问题：硬币对应于完全平方数。因此我们先计算好小于n的完全平方数，接下来通过动态规划数组dp[n]来计算，其中dp[i]代表正整数i最少组成个数。当当前完全平方数x小于整数i时，我们判断dp[i-x]+1与dp[i]的大小，如果dp[i-x]较小，则替换掉。另外dp[0]=0。
C++代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int numSquares(int n) { vector<int> pool; for(int i = 1; i*i <= n; i++){ pool.push_back(i*i); } int dp[10000] = {0}; dp[0] = 0; for(int i = 1; i <= n; i++){ dp[i] = i; for(int j = 0; j < pool.size(); j++){ if(pool[j] <= i){ dp[i] = dp[i] < dp[i - pool[j]] + 1 ? dp[i] : dp[i - pool[j]] + 1; } } } return dp[n]; } }; |
