在C ++中将N表示为1、3和4之和的不同方式的计数

给定正数N作为输入。目的是找到可以将N仅表示为1s，3s和4s之和的方式数量。例如，如果N为4，则可以将其表示为1 + 1 + 1 + 1、3 + 1、1 + 3、4，因此路数将为4。

让我们通过示例来理解。

例如

输入  -N = 5

输出-将N表示为1、3和4之和的不同方式的计数为：6

说明  -5可以表示为：

• 1 + 1 + 1 + 1 + 1

• 1 + 3 + 1

• 3 + 1 + 1

• 1 + 1 + 3

• 4 + 1

• 1 + 4

输入-N = 6

输出-将N表示为1、3和4之和的不同方式的计数为：9

说明-9可以表示为：

• 1 + 1 + 1 + 1 + 1 + 1

• 3 + 1 + 1 + 1

• 1 + 3 + 1 + 1

• 1 + 1 + 3 + 1

• 1 + 1 + 1 + 3

• 3 + 3

• 4 + 1 + 1

• 1 + 4 + 1

• 1 + 1 + 4

以下程序中使用的方法如下

在这种方法中，我们将使用动态编程方法来计算可以将N表示为1、3和4的方式的数目。取数组arr [i]（其中i表示数字，将arr [i]表示为数字）作为总和。

 基本情况将是 

arr [0] = 0（没办法）

arr [1] = 1（仅一种方式，1）

arr [2] = 1（仅一种方式，1 + 1）

arr [3] = 2（1 + 1 + 1，3）

现在其他数字4、5…i等将具有arr [i-1] + arr [i-3] + arr [i-4]的方式。

• 以正数N作为输入。 

• 函数Expres_sum(int N)取N并返回将N表示为1、3和4之和的不同方式的计数。

• 以数组arr [N + 1]来存储路数。

• 初始化基本情况arr [0] = 1，arr [1] = 1，arr [2] = 1和arr [3] = 2。

• 遍历其余值从i = 4到i <= N。

• 外卖arr [i]作为arr [i-1] + arr [i-3] + arr [i-4]的总和。

• 在for循环的末尾，返回arr [N]作为结果。

示例

#include <bits/stdc++.h>
using namespace std;
int Expres_sum(int N) {
   int arr[N + 1];
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 1;
   arr[3] = 2;
   for (int i = 4; i <= N; i++) {
      arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4];
   }
   return arr[N];
}
int main() {
   int N = 5;
   cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N);
   return 0;
}

如果我们运行上面的代码，它将生成以下输出-

输出结果

Count of different ways to express N as the sum of 1, 3 and 4 are: 6