snapchat 挂经

phantom 发表于 2016-2-19 12:03
这题意思就和走楼梯一样的。。只是一般走楼梯要么走一步要么走两步。。他这相当于规定你可以走{1,2,3,4} ...

赞！！！
凑字，凑字

可以用完全背包的解法来做吗？

panlong222 发表于 2016-2-19 11:43
你这个属于brute force了。。。
首先，其实用dfs也可以做到直接把所有的解枚举出来的。这个并不难想。
...

这样感觉就好简单啊 。。。

应该是走楼梯吧：

        int findComb(vector<int>& candidates, int n) {
                std::sort(candidates.begin(), candidates.end());
                vector<int> dp(n + 1, 0);
                dp[0] = 1;
                for (int i = 1; i < n + 1; i++) {
                        for (int j = 0; j < candidates.size(); j++) {
                                if (i <= candidates[j])
                                        dp[i] += dp[i - candidates[j]];
                                else
                                        break;
                        }
                }
                return dp[n];
        }

bentison90 发表于 2016-2-24 08:23
应该是走楼梯吧：

        int findComb(vector& candidates, int n) {

能想到走楼梯 这题就迎刃而解了~

好吧，经地里小伙伴们提醒，这题就是个走楼梯的题。大家可以无视我这么多的分析了- -菜是原罪啊

panlong222 发表于 2016-3-2 06:55
好吧，经地里小伙伴们提醒，这题就是个走楼梯的题。大家可以无视我这么多的分析了- -菜是原罪啊

应该是想太复杂了，其实加上红字更加简单。就是一维dp, 没有红字就是lz说的二维dp了。

nothingtrouble 发表于 2016-3-4 12:25
应该是想太复杂了，其实加上红字更加简单。就是一维dp, 没有红字就是lz说的二维dp了。

你这话楼主爱听~

请问这题有负输入怎么处理？

william_gong 发表于 2016-3-4 23:04
请问这题有负输入怎么处理？

应该不会有负数的，不然[-1,1],target=1 可以有无穷种方法