算法题/斐波那契数列：数因

题目

给定一个数字n，实现一个方法来计算有多少种可能的方式将n表示为1,3，或4的总和。

题解

基础解法

Java

class ExpressNumber {

  public int CountWays(int n) {
    if( n == 0)
      return 1; // 基础情况，我们不需要去减任何东西，因此只有一种解法

    if(n == 1)
      return 1; // 我们可以减去1然后剩下0，这是唯一解法

    if(n == 2)
      return 1; // 我们可以减去1两次，这是唯一解法

    if(n == 3)
      return 2; // '3' 能被表达成 {1,1,1}, {3}
      
    // 减去1，剩下 'n-1'
    int subtract1 = CountWays(n-1);
    // 减去3，剩下 'n-3'
    int subtract3 = CountWays(n-3);
    // 减去4，剩下 'n-1'
    int subtract4 = CountWays(n-4);

    return subtract1 + subtract3 + subtract4;
  }

  public static void main(String[] args) {
    ExpressNumber en = new ExpressNumber();
    System.out.println(en.CountWays(4));
    System.out.println(en.CountWays(5));
    System.out.println(en.CountWays(6));
  }
}

JavaScript

class ExpressNumber {
  countWays(n) {
    if (n === 0)
      return 1;

    if (n === 1)
      return 1;

    if (n === 2)
      return 1;

    if (n === 3)
      return 2;

    const subtract1 = this.countWays(n - 1);
    const subtract3 = this.countWays(n - 3);
    const subtract4 = this.countWays(n - 4);

    return subtract1 + subtract3 + subtract4;
  }
}

const en = new ExpressNumber();
console.log(en.countWays(4));
console.log(en.countWays(5));
console.log(en.countWays(6));

Python

class ExpressNumber:
  def count_ways(self, n):
    if n == 0:
      return 1

    if n == 1:
      return 1

    if n == 2:
      return 1

    if n == 3:
      return 2

    subtract1 = self.count_ways(n - 1)
    subtract3 = self.count_ways(n - 3)
    subtract4 = self.count_ways(n - 4)

    return subtract1 + subtract3 + subtract4

en = ExpressNumber()
print(en.count_ways(4))
print(en.count_ways(5))
print(en.count_ways(6))

Go

package main

import "fmt"

type ExpressNumber struct{}

func (en ExpressNumber) countWays(n int) int {
	if n == 0 {
		return 1
	}

	if n == 1 {
		return 1
	}

	if n == 2 {
		return 1
	}

	if n == 3 {
		return 2
	}

	subtract1 := en.countWays(n - 1)
	subtract3 := en.countWays(n - 3)
	subtract4 := en.countWays(n - 4)

	return subtract1 + subtract3 + subtract4
}

func main() {
	en := ExpressNumber{}
	fmt.Println(en.countWays(4))
	fmt.Println(en.countWays(5))
	fmt.Println(en.countWays(6))
}

自顶向下

Java

class ExpressNumber {

  public int CountWays(int n) {
    int dp[] = new int[n + 1];
    return CountWaysRecursive(dp, n);
  }

  public int CountWaysRecursive(int[] dp, int n) {
    if( n == 0)
      return 1; // 基础情况，我们不需要去减任何东西，因此只有一种解法

    if(n == 1)
      return 1; // 我们可以减去1然后剩下0，这是唯一解法

    if(n == 2)
      return 1; // 我们可以减去1两次，这是唯一解法

    if(n == 3)
      return 2; // '3' 能被表达成 {1,1,1}, {3}

    if (dp[n] == 0) {
        // 减去1，剩下 'n-1'
        int subtract1 = CountWays(n-1);
        // 减去3，剩下 'n-3'
        int subtract3 = CountWays(n-3);
        // 减去4，剩下 'n-4'
      int subtract4 = CountWaysRecursive(dp, n - 4);
      dp[n] = subtract1 + subtract3 + subtract4;
    }

    return dp[n];
  }

  public static void main(String[] args) {
    ExpressNumber en = new ExpressNumber();
    System.out.println(en.CountWays(4));
    System.out.println(en.CountWays(5));
    System.out.println(en.CountWays(6));
  }
}

JavaScript

class ExpressNumber {
  countWays(n) {
    if (n === 0)
      return 1;

    if (n === 1)
      return 1;

    if (n === 2)
      return 1;

    if (n === 3)
      return 2;

    const subtract1 = this.countWays(n - 1);
    const subtract3 = this.countWays(n - 3);
    const subtract4 = this.countWays(n - 4);

    return subtract1 + subtract3 + subtract4;
  }
}

const en = new ExpressNumber();
console.log(en.countWays(4));
console.log(en.countWays(5));
console.log(en.countWays(6));

Python

class ExpressNumber:
  def count_ways(self, n):
    if n == 0:
      return 1

    if n == 1:
      return 1

    if n == 2:
      return 1

    if n == 3:
      return 2

    subtract1 = self.count_ways(n - 1)
    subtract3 = self.count_ways(n - 3)
    subtract4 = self.count_ways(n - 4)

    return subtract1 + subtract3 + subtract4

en = ExpressNumber()
print(en.count_ways(4))
print(en.count_ways(5))
print(en.count_ways(6))

Go

package main

import "fmt"

type ExpressNumber struct{}

func (en ExpressNumber) countWays(n int) int {
	if n == 0 {
		return 1
	}

	if n == 1 {
		return 1
	}

	if n == 2 {
		return 1
	}

	if n == 3 {
		return 2
	}

	subtract1 := en.countWays(n - 1)
	subtract3 := en.countWays(n - 3)
	subtract4 := en.countWays(n - 4)

	return subtract1 + subtract3 + subtract4
}

func main() {
	en := ExpressNumber{}
	fmt.Println(en.countWays(4))
	fmt.Println(en.countWays(5))
	fmt.Println(en.countWays(6))
}

自底向上

Java

class ExpressNumber {

  public int CountWays(int n) {
    if( n <= 2 ) return 1;
    if( n == 3 ) return 2;

    int dp[] = new int[n+1];
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;

    for(int i=4; i<=n; i++)
      dp[i] = dp[i-1] + dp[i-3] + dp[i-4];

    return dp[n];
  }

  public static void main(String[] args) {
    ExpressNumber en = new ExpressNumber();
    System.out.println(en.CountWays(4));
    System.out.println(en.CountWays(5));
    System.out.println(en.CountWays(6));
  }
}

JavaScript

class ExpressNumber {
  countWays(n) {
    if (n <= 2) return 1;
    if (n === 3) return 2;

    const dp = new Array(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;

    for (let i = 4; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 4];
    }

    return dp[n];
  }
}

const en = new ExpressNumber();
console.log(en.countWays(4));
console.log(en.countWays(5));
console.log(en.countWays(6));

Python

class ExpressNumber:
  def count_ways(self, n):
    if n <= 2:
      return 1
    if n == 3:
      return 2

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 1
    dp[3] = 2

    for i in range(4, n + 1):
      dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 4]

    return dp[n]

en = ExpressNumber()
print(en.count_ways(4))
print(en.count_ways(5))
print(en.count_ways(6))

Go

package main

import "fmt"

type ExpressNumber struct{}

func (en *ExpressNumber) countWays(n int) int {
	if n <= 2 {
		return 1
	}
	if n == 3 {
		return 2
	}

	dp := make([]int, n+1)
	dp[0] = 1
	dp[1] = 1
	dp[2] = 1
	dp[3] = 2

	for i := 4; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-3] + dp[i-4]
	}

	return dp[n]
}

func main() {
	en := &ExpressNumber{}
	fmt.Println(en.countWays(4))
	fmt.Println(en.countWays(5))
	fmt.Println(en.countWays(6))
}