讨论/《滴滴历届编程题真题》 - 排列小球/
《滴滴历届编程题真题》 - 排列小球
共 5 个回复

package com.itcv.demo.other;

import java.util.Arrays;

class GFG
{

static final int MAX = 100;
  
// table to store to store results of subproblems
static int dp[][][][] = new int[MAX][MAX][MAX][3];
  
// Returns count of arrangements
// where last placed ball is
// 'last'. 'last' is 0 for 'p',
// 1 for 'q' and 2 for 'r'
static int countWays(int p, int q, int r, int last)
{
    // if number of balls of any 
    // color becomes less than 0
    // the number of ways arrangements is 0.
    if (p < 0 || q < 0 || r < 0)
    return 0;
  
    // If last ball required is 
    // of type P and the number
    // of balls of P type is 1 
    // while number of balls of
    // other color is 0 the number 
    // of ways is 1.
    if (p == 1 && q == 0 && r == 0 && last == 0)
        return 1;
  
    // Same case as above for 'q' and 'r'
    if (p == 0 && q == 1 && r == 0 && last == 1)
        return 1;
      
    if (p == 0 && q == 0 && r == 1 && last == 2)
        return 1;
  
    // If this subproblem is already evaluated
    if (dp[p][q][r][last] != -1)
        return dp[p][q][r][last];
  
    // if last ball required is P and 
    // the number of ways is the sum
    // of number of ways to form sequence
    // with 'p-1' P balls, q Q balss and
    // r R balls ending with Q and R.
    if (last == 0)
    dp[p][q][r][last] = countWays(p - 1, q, r, 1) + 
                        countWays(p - 1, q, r, 2);
  
    // Same as above case for 'q' and 'r'
    else if (last == 1)
    dp[p][q][r][last] = countWays(p, q - 1, r, 0) + 
                        countWays(p, q - 1, r, 2);
    //(last==2)
    else 
    dp[p][q][r][last] = countWays(p, q, r - 1, 0) + 
                        countWays(p, q, r - 1, 1);
  
    return dp[p][q][r][last];
}
  
// Returns count of required arrangements
static int countUtil(int p, int q, int r)
{
    // Initialize 'dp' array
    for (int[][][] row : dp)
    {
        for (int[][] innerRow : row) 
        {
            for (int[] innerInnerRow : innerRow)
            {
                Arrays.fill(innerInnerRow, -1);
            }
        }
    };
  
    // Three cases arise:
    return countWays(p, q, r, 0) + // Last required balls is type P
        countWays(p, q, r, 1) +    // Last required balls is type Q
        countWays(p, q, r, 2);       // Last required balls is type R
}

// Driver code
public static void main(String[] args)
{
    int p = 2, q = 1, r = 1;
  System.out.print(countUtil(p, q, r));

}

}

import java.util.Scanner;

class Solution{

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int[] n = new int[3];
    n[0] = in.nextInt();
    n[1] = in.nextInt();
    n[2] = in.nextInt();
    
    long[][][][] dp = new long[3][n[0] + 1][n[1] + 1][n[2] + 1];
    dp[0][1][0][0] = 1L;
    dp[1][0][1][0] = 1L;
    dp[2][0][0][1] = 1L;

    for (int i = 0; i <= n[0]; i++) {
        for (int j =0; j <= n[1]; j++) {
            for (int k = 0 ;k <= n[2];k++) {    
                dp[0][i][j][k] = Math.max(dp[0][i][j][k], (i - 1 < 0) ? (0L) : (dp[1][i - 1][j][k] + dp[2][i - 1][j][k]));
                dp[1][i][j][k] = Math.max(dp[1][i][j][k], (j - 1 < 0) ? (0L) : (dp[0][i][j - 1][k] + dp[2][i][j - 1][k]));
                dp[2][i][j][k] = Math.max(dp[2][i][j][k], (k - 1 < 0) ? (0L) : (dp[0][i][j][k - 1] + dp[1][i][j][k - 1])); 

            }
        }
    }       
    System.out.println(dp[0][n[0]][n[1]][n[2]] + dp[1][n[0]][n[1]][n[2]] + dp[2][n[0]][n[1]][n[2]]);
}

}

额,超时

    import java.util.*;    

    class Solution {
        private static int count = 0;
        
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            int a = s.nextInt(), b = s.nextInt(), c = s.nextInt();
            s.close();
            
            dfs(a-1, b, c, null);
            dfs(a, b-1, c, true);
            dfs(a, b, c-1, false);
            System.out.println(count);
        }
        
        private static void dfs(int a, int b, int c, Boolean now) {
            if (now == null) {
                if (b > 0) dfs(a, b-1, c, true);
                if (c > 0) dfs(a, b, c-1, false);
            } else if (now) {
                if (a > 0) dfs(a-1, b, c, null);
                if (c > 0) dfs(a, b, c-1, false);
            } else {
                if (a > 0) dfs(a-1, b, c, null);
                if (b > 0) dfs(a, b-1, c, true);  
            }
            if (a == 0 && b == 0 && c == 0) count++;
        }
    }

c++ 超时,我哭了

#include<iostream>
#include<vector>
using namespace std;
int bs[3];
int n;
int ans;
vector<int> tmp;

void dfs(int step){
    if(tmp.size() == n){
        ans += 1;
        return;
    }
    for(int i=0;i<3;i++){
        if(bs[i]>0 && i != tmp.back()){
            tmp.push_back(i);
            bs[i] -= 1;
            dfs(step + 1);
            bs[i] += 1;
            tmp.pop_back();
        }
    }
}
void solve(){
    cin>>bs[0]>>bs[1]>>bs[2];
    n = bs[0] + bs[1] + bs[2];
    ans = 0;
    for(int i=0;i<3;i++){
        if(bs[i]>0){
            tmp.push_back(i);
            bs[i]-=1;
            dfs(1);
            bs[i] +=1;
            tmp.pop_back();
        }
    }
    cout<<ans;
}
int main(){
    solve();
    return 0;
}

Python3 记忆化搜索

memo = {}
def dfs(pre, p, q, r) :
    if p+q+r==0 : return 1
    if memo.get((pre, p, q, r)) != None : return memo[pre, p, q, r]
    ret = 0
    if pre!=0 and p>0 : ret += dfs(0, p-1, q, r)
    if pre!=1 and q>0 : ret += dfs(1, p, q-1, r)
    if pre!=2 and r>0 : ret += dfs(2, p, q, r-1)
    memo[pre, p, q, r] = ret
    return ret

[np, nq, nr] = [int(x) for x in input().split(' ') if x.isdigit()]
ans = 0
if np>0 : ans += dfs(0, np-1, nq, nr)
if nq>0 : ans += dfs(1, np, nq-1, nr)
if nr>0 : ans += dfs(2, np, nq, nr-1)
print(ans)