一个简单的 dp，排序内容和广告

rerank ads and contents.ipynb

{
  "cells": [
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2021-02-08T18:18:13.026660Z",
          "end_time": "2021-02-08T18:18:13.033652Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "from random import random\nfrom math import floor",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2021-02-08T18:23:21.074765Z",
          "end_time": "2021-02-08T18:23:21.080762Z"
        },
        "scrolled": true,
        "trusted": true
      },
      "cell_type": "code",
      "source": "# return the solution of max sequence\nm = 11\nn = 5\nassert m >= n\nscores = [[floor(random() * 10) for _ in range(n)] for _ in range(m)]",
      "execution_count": 37,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2021-02-08T18:23:21.361025Z",
          "end_time": "2021-02-08T18:23:21.371016Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "scores",
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 38,
          "data": {
            "text/plain": "[[3, 3, 0, 4, 9],\n [4, 2, 3, 5, 0],\n [0, 8, 5, 4, 7],\n [2, 2, 3, 6, 6],\n [6, 2, 1, 5, 3],\n [8, 0, 7, 2, 7],\n [5, 5, 1, 8, 4],\n [9, 3, 4, 6, 9],\n [1, 1, 7, 7, 6],\n [5, 3, 2, 7, 2],\n [6, 0, 2, 2, 0]]"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2021-02-08T18:23:21.663968Z",
          "end_time": "2021-02-08T18:23:21.711938Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "def find_max_reward(scores):\n    m, n = len(scores), len(scores[0])\n\n    for i in range(1, m):\n        scores[i][0] = max(scores[i - 1][0], scores[i][0])\n\n    for i in range(1, m):\n        for j in range(1, min(n, i + 1)):\n            scores[i][j] = max(scores[i - 1][j],\n                               scores[i - 1][j - 1] + scores[i][j])\n\n    result, p = [], m - 1\n    for j in range(n - 1, -1, -1):\n        while p >= 1 and scores[p][j] == scores[p - 1][j]:\n            p -= 1\n        result.append(p)\n        p -= 1\n    return scores[-1][-1], result[::-1]",
      "execution_count": 39,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2021-02-08T18:23:21.982562Z",
          "end_time": "2021-02-08T18:23:21.989558Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "find_max_reward(scores)",
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 40,
          "data": {
            "text/plain": "(36, [1, 2, 5, 6, 7])"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2021-02-08T18:23:22.412239Z",
          "end_time": "2021-02-08T18:23:22.420235Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "scores",
      "execution_count": 41,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 41,
          "data": {
            "text/plain": "[[3, 3, 0, 4, 9],\n [4, 5, 3, 5, 0],\n [4, 12, 10, 4, 7],\n [4, 12, 15, 16, 6],\n [6, 12, 15, 20, 19],\n [8, 12, 19, 20, 27],\n [8, 13, 19, 27, 27],\n [9, 13, 19, 27, 36],\n [9, 13, 20, 27, 36],\n [9, 13, 20, 27, 36],\n [9, 13, 20, 27, 36]]"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "_draft": {
      "nbviewer_url": "https://gist.github.com/172f2e5cb8dab372e14e1d73ce8566a6"
    },
    "gist": {
      "id": "172f2e5cb8dab372e14e1d73ce8566a6",
      "data": {
        "description": "一个简单的 dp，排序内容和广告",
        "public": true
      }
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.6.8",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "varInspector": {
      "window_display": false,
      "cols": {
        "lenName": 16,
        "lenType": 16,
        "lenVar": 40
      },
      "kernels_config": {
        "python": {
          "library": "var_list.py",
          "delete_cmd_prefix": "del ",
          "delete_cmd_postfix": "",
          "varRefreshCmd": "print(var_dic_list())"
        },
        "r": {
          "library": "var_list.r",
          "delete_cmd_prefix": "rm(",
          "delete_cmd_postfix": ") ",
          "varRefreshCmd": "cat(var_dic_list()) "
        }
      },
      "types_to_exclude": [
        "module",
        "function",
        "builtin_function_or_method",
        "instance",
        "_Feature"
      ]
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}