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