讨论/技术交流/【求助】leetcode 322题同一样例 测试正确 提交超时???/
【求助】leetcode 322题同一样例 测试正确 提交超时???
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        int dp[n + 1][amount + 1];
        for(int j = 1; j <= amount; j++){
            dp[0][j] = -1;
        }
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                int minVal = INT_MAX;
                int cnt;
                for(cnt = 0; j - cnt * coins[i - 1] >= 0; cnt++){
                    if(dp[i - 1][j - cnt * coins[i - 1]] == -1) continue;
                    minVal = min(minVal, dp[i - 1][j - cnt * coins[i - 1]] + cnt);
                }
                dp[i][j] = minVal == INT_MAX ? -1 : minVal;
            }
        }
        return dp[n][amount];
    }
};

测试正确:
截屏2021-04-14 下午10.19.27.png

提交错误:
截屏2021-04-14 下午10.21.34.png

有大佬知道为啥吗??????????

1
共 8 个回复

确实,有道理

1

感谢 我也觉得可能是我那个写法太慢超时了

1

别用数组,用vector

1

超时了

1

写的有点复杂可能超时了吧
我写一个简单点的

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, 1e9);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(auto c : coins){
                if(c > i) continue;
                dp[i] = min(dp[i], dp[i - c] + 1);

            }
        }
        return dp[amount] == 1e9 ? -1 : dp[amount];
    }
};
1

后面的用例超时了,显示的超时用例有问题

抱歉,试了一下应该是时间复杂度过高了,可以看一下题解更好的解法,另外,leetcode在github是有feedback项目的,可以去上面提issue

感谢, 不过改成vector好像还是超时