以下题目均来自leetcode、poj
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶 示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
//第i阶的爬法数量 = 第i-1阶的爬法数量 + 第i-2阶的爬法数量
class Solution {
public:
int climbStairs(int n) {
std::vector<int> dp(n+3,0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2:
输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 贡献者
/*
第一，偷第1家，然后第二家就显然不能偷了，从第3家开始往后，假如有一种最大的偷法，加上第1家偷的，就是最后的结果；
第二，不偷第1家，从第2家开始往后，假如有一种最大的偷法，就是最后的结果；
这两种偷法里面，比较大的一种，就是最后的结果。
*/
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0){
return 0;
}
if(nums.size() == 1){
reuturn nums[0];
}
std::vector<int> dp(nums.size(),0);
dp[0] = nums[0];
dp[1] = std::max(nums[0],nums[1]);
for(int i = 2;i < nums.size();i++){
dp[i] = std::max(dp[i-1],dp[i-2]+nums[i])
}
return dp[nums.size() - 1];
}
};
最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
std::vector<int> dp(nums.size(),0);
dp[0] = nums[0];
int max_res = dp[0];
for (int i = 1; i < nums.size();i++){
dp[i] = std::max(dp[i-1]+nums[i],nums[i]);
if(max_res < dp[i]){
max_res = dp[i];
}
}
return max_res;
}
};
零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:
输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币的数量是无限的。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
std::vector<int> dp;
for (int i = 0; i < amount; i++) {
dp.push_back(-1);
}
dp[0] = 0;
for (int i = 0;i <= amount;i++) {
for (int j = 0;j < amount;j++){
if(i - coins[j] >= 0 && dp[i - coins[j]] != -1){
if(dp[i] == -1 || dp[i] > dp[i - coins[j] + 1]){
dp[i] = dp[i - coins[j]] + 1;
}
}
}
}
return dp[amount];
}
};
三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
//自底向上
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.size() == 0){
return 0;
}
std::vector<std::vector<int>> dp;
for(int i = 0; i < triangle.size();i++){
dp.push_back(std::vector<int>())
for(int j = 0; j < triangle.size();j++){
dp[i].push_back(0);
}
}
for(int i = 0; i < dp.size();i++){
dp[dp.size()-1][i] = triangle[dp.size-1][i];
}
for (int i= dp.size() - 2;i >= 0;i--){
for(int j = 0; j < dp.size();j++){
dp[i][j] = std::min(dp[i+1][j],dp[i+1][j+1]+triangle[i][j]);
}
}
return dp[0][0];
}
};
最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 0) return 0;
std::vector<int> dp(nums.size(),0);
dp[0] = 1;
int LIS = 1;
for(int i = 1;i < dp.size();i++){
dp[i] = 1;
for(int j = 0; j < i;j++){
if(nums[i] > nums[j] && dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
}
}
if(LIS < dp[i]){
LIS = dp[i];
}
}
return LIS;
}
};
最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == 0){
return 0;
}
int row = grid.size();
itn col = grid[0].size();
std:vector<std::vector<int>> dp(row,std::vector<int>(col,0));
dp[0][0] = grid[0][0];
for(int i = 1; i < col; i++){
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for(int i =1; i < row; i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
for(int j = 1; j < col; j++){
dp[i][j] = std::min(dp[i-1][j],dp[i][j-1] + grid[i][j]);
}
}
return dp[row-1][col-1];
}
};
地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
-2 (K) -3 3 -5 -10 1 10 30 -5 (P)
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。 贡献者
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if(dungeon.size() == 0){return 0;}
std::vector<std::vector<int> dp(dungeon.size(),std::vector<int>(dungeon[0].size(),0));
int row = dungeon.size();
int col = dungeon[0].size();
dp[row-1][col-1] = std::max(1,1-dungeon[row-1][col-1]);
for(int i = col-2; i >= 0; i--){
dp[row -1][i] = std::max(1,dp[row -1][i+1] - dungeon[row -1][i]);
}
for(int i = row-w2; i >=0;i--){
dp[i][col - 1] = std::max(1,dp[i+1][col - 1] - dungeon[i][col - 1]);
}
for(int i = row-2; i >=0;i--){
for(int j = col-2; j >=0;j--){
int dp_min = std::min(dp[i+1][j],dp[i][j+1]);
dp[i][j] = std::max(1,dp_min - dungeon[i][j]);
}
}
return dp[0][0];
}
};
