面试- Oracle

Question

在一个游戏中，唯一可以得分的是2,3,4,5,6,7,8，并且它们可以被任意次数地得分

团队可以玩的组合的总数是多少，团队可以达到的分数是50。

示例8，8，8，8，8，2是有效的8，8，8，8，4，4，2也是有效的。等等。

Answer 1

这个问题可以用动态规划来解决，有两个参数：

• i -我们拥有considered
• s的索引-总分。

f(i, s)将包含获得s分数的方法总数。

假设score[]是可以取得的唯一正分数的列表。

DP解决方案的配方：

f(0, s) = 1, for all s divisible to score[0]
f(0, s) = 0, otherwise

f(i + 1, s) = Sum [for k = 0 .. floor(s/score[i + 1])] f(i, s - score[i + 1] * k)

Answer 2

这看起来像是硬币兑换的问题。不久前我为它写了一些Python代码。

编辑的解决方案：

from collections import defaultdict

my_dicto = defaultdict(dict)

def row_analysis(v, my_dicto, coins):
    temp = 0
    for coin in coins:
        if v >= coin:
            if v - coin == 0: # changed from if v - coin in (0, 1):
                temp += 1
                my_dicto[coin][v] = temp
            else:                
                temp += my_dicto[coin][v - coin]
                my_dicto[coin][v] = temp
        else:
            my_dicto[coin][v] = temp
    return my_dicto

def get_combs(coins, value):
    '''
    Returns answer for coin change type problems.
    Coins are assumed to be sorted.

    Example:
        >>> get_combs([1,2,3,5,10,15,20], 50)
        2955
    '''
    dicto = defaultdict(dict)

    for v in xrange(value + 1):
        dicto = row_analysis(v, dicto, coins)

    return dicto[coins[-1]][value]

在您的案例中：

>>> get_combs([2,3,4,5,6,7,8], 50)
3095

Answer 3

这就像访问一个7分支决策树。

代码是：

class WinScore{
static final int totalScore=50;
static final int[] list={2,3,4,5,6,7,8};
public static int methodNum=0;

static void visitTree( int achieved , int index){
        if (achieved >= totalScore ){
                return;
        }
        for ( int i=index; i< list.length; i++ ){
                if ( achieved + list[i] == totalScore ) {
                        methodNum++;
                }else if (  achieved + list[i] < totalScore ){
                        visitTree( achieved + list[i], i );
                }
        }
}
public static void main( String[] args ){
        visitTree(0, 0);
        System.out.println("number of methods are:" + methodNum );

}
}
output:
number of methods are:3095