⭐⭐⭐【爬楼梯问题变形】LeetCode 300. Longest Increasing Subsequence

题目描述

知识点

动态规划

结果

实现

码前思考

1. 采用自下而上的方式进行递推。跟爬楼梯问题一毛一样。

代码实现

//采用递推的方式进行，其实也可以使用递归，但是感觉差不多吧，反正是分解子问题。递推时间复杂度应该要高些
//对于最优化问题，我们应该要想到dp才对
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0){
            return 0;
        }

        vector<int> dp(amount+1,INT_MAX);

        //dp数组初始化,
        for(int coin : coins){
            if(coin <= amount){//这里有玄机！
                dp[coin] = 1;
            }  
        }

        for(int cur = 1;cur <= amount;cur++){
            for(int coin : coins){
                if(cur > coin && dp[cur-coin] != INT_MAX){//如果大于的话,而且还是有选择的话
                    dp[cur] = min(dp[cur],dp[cur-coin]+1);
                }
            }
        }

        if(dp[amount] == INT_MAX){
            return -1;
        }else{
            return dp[amount];
        }
    }
};

码后反思

1. 看【结果】可以知道，我第一次提交出错了，原因在于我没有考虑到硬币面值coin可能大于amount的情况，所以导致了数组越界的发生！之前的错误代码如下：

   //采用递推的方式进行，其实也可以使用递归，但是感觉差不多吧，反正是分解子问题。递推时间复杂度应该要高些
   //对于最优化问题，我们应该要想到dp才对
   class Solution {
   public:
       int coinChange(vector<int>& coins, int amount) {
           if(amount == 0){
               return 0;
           }
   
           vector<int> dp(amount+1,INT_MAX);
   
           //dp数组初始化
           for(int coin : coins){  
               dp[coin] = 1;
           }
   
           for(int cur = 1;cur <= amount;cur++){
               for(int coin : coins){
                   if(cur > coin && dp[cur-coin] != INT_MAX){//如果大于的话,而且还是有选择的话
                       dp[cur] = min(dp[cur],dp[cur-coin]+1);
                   }
               }
           }
   
           if(dp[amount] == INT_MAX){
               return -1;
           }else{
               return dp[amount];
           }
       }
   };
   

   如上代码所示，dp设置为amount+1，那么dp[coin]很有可能会数组越界！！！
2. 其次，我还忘记了下面这个条件的书写：
   
   导致也出现了错误，要考虑不能找零的子问题啊！！！
3. 反正这道题我思想会，就是有点走神了（可能因为今天生日，飘了，哈哈哈）。希望以后能够在写代码时认真思考！