leetcode动态规划--基础题

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

思路

根据题目意思，最大跳跃距离，说明可以跳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;

    }

};

巴特西

leetcode动态规划--基础题

跳跃游戏

思路

代码

不同路径

思路

代码

零钱兑换

思路

代码

Longest Increasing Subsequence

思路

代码

最新文章

热门文章