动态规划问题的理解
1.动态规划问题的定义和应用?
1.Dynamic programming, solves problems by combining the solutions to subproblems.
2.Dynamic programming applies when subproblems overlap-that is, when subproblems share subproblems.
3.A dynamic-programming algorithm solves each subsubproblems just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every > time it solves each subsubproblem.
4.Divide-and-Conquer also solves problems by combining the solutions to subproblems. It partition the problem into disjoint method, solve the subproblems recursively, and then compute their solutions to solve the original problem. A divide-and-conquer algorithm does more work than necessary, repeatedly solve the common subsubproblems.
intuitively,
1.动态规划, 基础思想是通过 [组合子问题的解] 来 [得到原问题的解]
2.[动态规划] 针对性地考察在 [有重叠性的子问题] 之上, 也就是 [子问题] 之间有 [共享性] 或者 [重叠性], 也叫 [重叠性子问题] 或者 [公共子问题]
3.动态规划对每个子问题, 只 [解决一次], 不再多余计算 1 次; 将每个子问题的解记录在某个表里面, 我们称之为 [备忘录]; 这种 [借助备忘录保存子问题的结果] 的方式, 避免了 [解决子问题的子问题] 过程中带来的重复计算
4.分治算法, 基础思想也是通过 [组合子问题的解] 来 [得到原问题的解]; 但是分治算法, 对于每个子问题, 没有 [只解决一次] 这种保证, 在解决子问题的时候, 不可避免地会重复计算
Dynamic programming typically applies to optimization problems. Such problems can have many possible solutions. Each solution has a value, and you want to find a solution with the optimal (minimum or maximum) value.
intuitively,
1.动态规划通常应用在 [优化问题]: 问题本身包含多个 [可行解] 的情况下, 求 [最值] 的情形, 比如求最大值或者最小值; 经典的动态规划问题均属于这一类问题: 最长递增子序列, 最长公共子序列, 最大子数组和等
To devolop a dynamic-programming algorithm, follow a sequence of four steps:
1.Characterize the structure of an optimal solution.
2.Recursively define the value of an optimal solution.
3.Compute the value of an optimal solution, typically in a bottom-up fashion.
4.Construct an optimal solution from computed information.
Steps 1-3 from the basis of a dynamic-programming solution to a problem. If you need only the value of an optimal solution, and not he solution itself, then you can omit step4. When you do perform step4, it oftens pays to maintain additional information during step3 so that you can easily construct an optimal solution.
通过斐波那契数问题理解动态规划问题
509.斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1. 给定 n ，请计算 F(n) 。
示例 1：输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
class Solution {
public:
vector<int> dp;
int fib(int n) {
dp.resize(n + 1);
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
当然这个问题还可以用滚动数组优化到 O(1) 空间复杂度
class Solution {
public:
int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int minus2 = 0;
int minus1 = 1;
int ans = 0;
for (int i = 2; i <= n; ++i) {
ans = minus2 + minus1;
minus2 = minus1;
minus1 = ans;
}
return ans;
}
};
1035.不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：nums1[i] == nums2[j] 且绘制的直线不与任何其他连线（非水平线）相交。 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。 k以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：输入：nums1 = [1,4,2], nums2 = [1,2,4] 输出：2 [1,4,2] [1,2,4] 解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2：输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2] 输出：3
示例 3：输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1] 输出：2
分析:
1.两个数组可以看成两个序列, 以某种方式对齐, 如果相等那么就算一个; 如果能想到是相当于找nums1和nums2的最长公共子序列, 那么问题可解
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if (m == 0 || n == 0)
return 0;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (nums1[i-1] == nums2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
};
583.两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步 可以删除任意一个字符串中的一个字符。
示例 1：输入: word1 = “sea”, word2 = “eat” 输出: 2 解释: 第一步将 “sea” 变为 “ea” ，第二步将 “eat “变为 “ea”
示例 2: 输入：word1 = “leetcode”, word2 = “etco” 输出：4
分析:
1.状态是 dp[i][j] 表示 word1[0..i] 和 word2[0..j] 之间的删除最小步数
2.如果当前比较的字符是相同的, 那么删除最小步数就是两边前一个继承过来的, if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]
3.如果当前比较的字符是不相同, 要么word1删除1个不相同字符, 要么word2删除1个不相同字符, 两类删除操作都是需要+1, if(word1[i-1] != word2[j-1]) dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)
4.边界条件dp[i][0] = i表示word1和空字符串的删除最小步数, dp[0][j] = j
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 0; i <= m; ++i) {
dp[i][0] = i;
}
for (int i = 0; i <= n; ++i) {
dp[0][i] = i;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);
}
}
}
return dp[m][n];
}
};
Reference
1.Introduction to Algorithm. 4th Edition.
转载请注明来源, from goldandrabbit.github.io
