{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "gpuType": "T4"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "UPxYY9I4LtvE"
      },
      "outputs": [],
      "source": [
        "import cupy as cp\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "N = 10000\n"
      ],
      "metadata": {
        "id": "22OtB9eULxVZ"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "dp = cp.zeros(N, dtype=cp.int32)\n"
      ],
      "metadata": {
        "id": "RLVBmhV2L1Gx"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "dp[0] = 1\n",
        "dp[1] = 1\n",
        "dp[2] = 1\n",
        "dp[3] = 2\n"
      ],
      "metadata": {
        "id": "iwdUORffMWm6"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "for i in range(4, N):\n",
        "    dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 4]\n"
      ],
      "metadata": {
        "id": "3wlBK-8WL3Z4"
      },
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "result = cp.asnumpy(dp)\n",
        "print(result[:20])"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bhQIS9nrMUWd",
        "outputId": "1daec245-5567-438a-d274-dcd62afdddc7"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[   1    1    1    2    4    6    9   15   25   40   64  104  169  273\n",
            "  441  714 1156 1870 3025 4895]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "jc4seEccNAnG"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}