跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
思路
根据题目意思，最大跳跃距离，说明可以跳0--nums[i]的距离
可以把跳跃看成走nums[i]步，如果能走到下一位置则可以加油获取更多的步数(nums[j]步），但是不能累加
那么只需扫一遍nums数组，更新剩余能跳的距离（注意不能累加，只能取最大！）
到终点之前判断是否有剩余步骤即可
代码
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.size()==0)return false;
int cur=nums[0];
for(int i=1;i<nums.size();++i){
if(cur<=0){
return false;
}
cur--;
cur=std::max(cur,nums[i]);
}
return true;
}
};
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
思路
当前位置可以来自上方或者左边
令dp[i][j]表示第i行第j列的路径数，则dp[i][j]=dp[i-1][j]+dp[i][j-1];
注意边界即可
代码
class Solution {
public:
int uniquePaths(int m, int n) {
int path[m+1][n+1];
memset(path,0,sizeof(path));
path[0][1]=1;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
path[i][j]=path[i-1][j]+path[i][j-1];
}
}
return path[m][n];
}
};
零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
思路
一开始想法是搜索，但是超时了（大概是我太菜了吧)
接着想到每一中硬币选的个数最多为amount / coins[i]
接着就是将其转化为0/1背包问题求解
dp[i][j]表示前i个硬币组成金额 j 的最少硬币个数
dp[i][j] = min(dp[i-1][j-k*coins[i]) , 0<=k<=j/coins[i];
代码
代码写的太丑了
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(coins.size()==0)return -1;
int cn=coins.size();
int dp[cn+1][amount+1];
for(int i=0;i<=cn;++i){
for(int j=0;j<=amount;++j){
dp[i][j]=-1;
}
}
for(int i=0;i<=cn;++i){
dp[i][0]=0;
}
// 第一个硬币
for(int i=1;i<=amount;++i){
if(i%coins[0]==0){
dp[0][i]=i/coins[0];
}
}
for(int i=1;i<cn;++i){
for(int j=0;j<=amount;++j){
// 第i枚硬币选择k个
for(int k=0;k*coins[i]<=j;++k){
if(dp[i-1][j-k*coins[i]]!=-1){
if(dp[i][j]==-1){
dp[i][j]=dp[i-1][j-k*coins[i]]+k;
}else{
dp[i][j]=min(dp[i][j],dp[i-1][j-k*coins[i]]+k);
}
}
}
}
}
return dp[cn-1][amount];
}
};Longest Increasing Subsequence
最长上升子串
思路
令dp[i]表示以nums[i]作为结尾的最大上升子序列的最大长度
内层循环在前面找比nums[i]小的元素，可以将nums[i]接到j后面使得LIS长度加1
dp[i] = max(dp[j]+1) ,nums[i]>nums[j]&&0<=j<i;
注意最后返回dp的最大值
代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()==0||nums.size()==1)return nums.size();
int dp[nums.size()];
for(int i=0;i<nums.size();++i){
dp[i]=1;
}
int ans=-1;
for(int i=0;i<nums.size();++i){
for(int j=0;j<i;++j){
if(nums[i]>nums[j]){
dp[i]=std::max(dp[i],dp[j]+1);
}
}
ans=std::max(ans,dp[i]);
}
return ans;
}
};
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
