{"trustable":false,"sections":[{"title":"描述","value":{"format":"MD","content":"此题考查动态规划思想\n首先我们需要把输入字符转换为数字a,b 然后使用动态规划求解A+B的值 最后输出答案\n我们可以设计出如下DP方程\n令f[j]表示i+j的值 则有 f[0][0]\u003d0\nf[j]\u003dmax\n{ f[i-1][j]+1,\nf[i][j-1]+1 } 由于对于每个i,j我们都要计算出f[j],因此时间复杂度与空间复杂度都为O(n^2)\n但是 对于题目提供的最大数字n\u003d32767明显超时!\n【优化1】\n对于DP方程 由于每次计算只需要f[i-1][j]或f[j-1]\n因此我们可以使用滚动数组优化DP的空间复杂度\n使用两个整数x,y分别保存f[i-1][j]与f[j-1]\n空间复杂度降为O(2) 然而时间复杂度O(n^2)仍然超时!\n“时间复杂度,到目前为止还没有更好的优化方法。因此,此题被称为史A+B Problem题解综述上最难的dp题!”\n【优化2】\n对于整数的运算 我们可以利用位运算的思想简化复杂度\n题目显然要我们求两非负整数之和。\n我们知道,在非负整数加法的二进制逻辑运算中,每一位上的结果取决于以下两方面:\n1、本位上两个逻辑位的异或值\n2、后一位的结果是否溢出\n利用这种性质,可以考虑如下做法:\n令f[j]表示,考虑两个加数的后i、j位相加的结果,显然有以下状态转移方程 f[j]\u003d max\n{ f[i][j-1]+y \u0026 (1 \u003c\u003c (j-1))\nf[i-1][j]+x \u0026 (1 \u003c\u003c (i-1)) }\n复制代码\n赋初值f[0][0]\u003d(x \u0026 1) ^ (y \u0026 1)\n两个循环变量i,j从1循环到log(2,maxint)\n我们成功的把时空复杂度降为O(log^2n)\n利用滚动数组,可以进一步把空间复杂度降为O(2)\n至此,我们得到了一个较为圆满的解答\n "}},{"title":"输入","value":{"format":"MD","content":"一行,包含两个整数A,B,中间用单个空格隔开。A和B均在整型范围内。"}},{"title":"输出","value":{"format":"MD","content":"一个整数,即A+B的值。保证结果在整型范围内。\n "}},{"title":"样例输入","value":{"format":"MD","content":"1 2"}},{"title":"样例输出","value":{"format":"MD","content":"3\n "}}]}