您正在查看： DP 分类下的文章
问题描述:
长江游艇俱乐部在长江上设置了 n 个游艇出租站 1, 2, …, n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i, j)（1≤i<j≤n）。试设计一个算法,计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> distance;
for (int i = 1; i < n; i++) {
vector<int> tmp;
tmp.reserve(n);
for (int j = 0; j < i; j++) {
tmp.push_back(0);
}
for (int j = i; j < n; j++) {
int t;
cin >> t;
tmp.push_back(t);
}
distance.push_back(tmp);
}
vector<int> ans = {0};
for (int i = 1; i < n; i++) {
int min = ans[i - 1] + distance[i - 1][i];
for (int j = 0; j < i; j++) {
min = min < ans[j] + distance[j][i] ? min : ans[j] + distance[j][i];
}
ans.push_back(min);
}
cout << ans[n - 1] << endl;
return 0;
}
2020-02-06 |HHR
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd" 输出: "bb"
class Solution {
public:
string longestPalindrome(string s) {
if (s.length() == 0) return "";
bool dp[1000][1000] = {{false}};
int max = 0;
string ans;
for (int x = s.length(); x >= 0; x--) {
for (int y = x; y < s.length(); y++) {
if (y - x < 2) {
dp[x][y] = s[x] == s[y];
} else {
dp[x][y] = dp[x + 1][y - 1] && (s[x] == s[y]);
}
if (dp[x][y] && y - x + 1 > max) {
max = y - x + 1;
ans = s.substr(x, y - x + 1);
}
}
}
return ans;
}
};第i到第j个char能否构成回文取决于 1.第i+1到第j-1个char是否回文 2.第i个char和第j个char是否相同 dp[i][j]=dp[i+1][j-1]&&s[i]==s[j] 注意考虑串为空的特殊情况 x自大到小，y从小到大，确保dp[x+1][y-1]已经完成定义
https://leetcode-cn.com/problems/longest-palindromic-substring/
2020-02-06 |HHR
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:
输入: [7,6,4,3,1] 输出: 0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.empty()) return 0;
int ans = 0, min = prices[0];
for (int price:prices) {
ans = max(ans, price - min);
if (price < min) min = price;
}
return ans;
}
};到某天为止的最大盈利=max(前一天为止的最大盈利,如果今天卖出的最大盈利) 注意没有任何交易日的特殊情况
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
2020-02-06 |HHR
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
class Solution {
public:
int climbStairs(int n) {
vector<int> ans;
ans.push_back(1);
ans.push_back(2);
for (int x = 2; x < n; x++) {
ans.push_back(ans[x - 1] + ans[x - 2]);
}
return ans[n-1];
}
};到每一阶的方法数是前两阶方法数之和
2020-02-06 |HHR
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution {
public:
int maxSubArray(vector<int> &nums) {
int sum = 0, max = nums[0];
for (int num:nums) {
if (sum < 0) sum = 0;
sum += num;
if (sum > max) max = sum;
}
return max;
}
};假设你是一个选择性遗忘的赌徒，数组表示你这几天来赢钱或者输钱， 你用sum来表示这几天来的输赢， 用ans来存储你手里赢到的最多的钱， 如果昨天你手上还是输钱（sum < 0），你忘记它，明天继续赌钱； 如果你手上是赢钱(sum > 0), 你记得，你继续赌钱； 你记得你手气最好的时候 作者：acnesu 链接：https://leetcode-cn.com/problems/maximum-subarray/solution/jia-she-ni-shi-yi-ge-du-tu-by-acnesu/ 来源：力扣（LeetCode）