KMP实战

旋转词问题

‘34512’就是‘12345’的一种旋转词,因此给定一个序列可以有多个旋转词,为了判断我们手上的一个序列A是否是
序列B的旋转词.可以考虑
‘1234512345’中找’34512’这个字串.采用KMP方法

斐波那契数列(矩阵乘法)

复杂度log(n)
当任何问题是递推式形式(固定递推),都存在log(n)的解。

因为递推系数固定,所以可以写成固定系数的矩阵相乘的形式.
由此变成了矩阵幂的问题

矩阵幂

打表法

斐波那契的另一种解题方法
何为打表法？
有时候与其重复运行同样的算法得出答案，还不如直接用算法把这组数据所有可能的答案都枚举出来存到一个足够大的容器中去-例如数组(打表)，然后再输入数据的时候，直接遍历容器，检索这个数据是否有题意要求的结果。
比如最常见的素数打表.
在此之前，我们判断素数的方法多是用暴力枚举法，即若要判断一个数n是否是素数，就需要从i=2开始，一直到n/2为止，判断是否有数能整除n，若没有的话，则n为素数。这样判断素数的方法有一个致命的弱点，就是容易超时，因为每判断一次都要从2开始一个一个作整除判断，一旦要判断的这个n稍大一点的话，这种方法就无能为力了。因此，这里引入一种新的判断素数的方法—打表判断法。
思路：先确定要判断的数大概在哪个范围之内，以便于开一个合适的数组prime[]，首先要将prime数组初始化为0，i从2开始，如果对应的prime[i]为0 的话，即从j=i*i开始，到最大的范围，将这些位置的prime的值都变为1，表示这些数都不是素数，这里注意j在加的时候加的不是1，而是i，这样一直下去，一张素数表就完成了，当需要判断某个数是否是素数的时候只要判断prime[i]的值是多少就可以了，如果是0，表示这个i是素数，如果是1，表示这个i不是素数。
下面是该函数的代码

void dabiao()
{
  memset(biao,0,sizeof(biao));  
  for(int i=2;i<=31623;++i)
 {  
   if(biao[i])   continue;
   for(int j=i*i;j<MAXSIZE;j+=i)
     {
       biao[j]=1;
     }
  }

def dabiao(biao):
  A=[0 for _ in range(biao)]
  for i in range(2,31623):
    if(A[i]==1):
      continue
    for j in range(i*i,MAXSIZE,i):
      A[j]=1

经典的斐波那契打表


/* JSK-4 简单斐波那契 */

#include <stdio.h>
#include <string.h>

#define N 50
int f[N + 1];

int fib_init(int n)
{
    f[0] = 0;
    f[1] = 1;
    int i;
    for(i = 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
}

int main()
{
    fib_init(N);

    int n;
    scanf("%d", &n);
    printf("%d\n", f[n]);
}

与传统的记忆递归方法相比的好处是,减少了重复计算.

M×N的砖块填充

剑指offer里的例题

状态压缩dp

动态规划的状态有时候比较恶心，不容易表示出来，需要用一些编码技术，把状态压缩的用简单的方式表示出来。
典型方式：当需要表示一个集合有哪些元素时，往往利用2进制用一个整数表示。
动态规划本来就很抽象，状态的设定和状态的转移都不好把握，而状态压缩的动态规划解决的就是那种状态很多，不容易用一般的方法表示的动态规划问题，这个就更加的难于把握了。难点在于以下几个方面：状态怎么压缩？压缩后怎么表示？怎么转移？是否具有最优子结构？是否满足后效性？涉及到一些位运算的操作，虽然比较抽象，但本质还是动态规划。找准动态规划几个方面的问题，深刻理解动态规划的原理，开动脑筋思考问题。这才是掌握动态规划的关键。

例题1

经典问题:TSP
一个n个点的带权的有向图,求一条路径,使得这条路经过每个点恰好一次,并且,路径上边的权值和最小(n<=16)
如何表示一个点集:
优于只有16个点,所以我们用一个整数表示一个点集:
5=0000000000000101(二进制表示)
它的第0位和第二位是,1表示这个点集里有2个点
所以一个整数i就表示了一个点集;
整数i可以表示一个点集也可以表示第i个点
状态表示:dp[i][j]表示经过点集i中的点恰好一次,不经过其他的点,并且以j点为终点,权值和的最小值,如果这个状态不存在,就是无穷大

状态转移:
单点集:状态存在dp[i][j]=0;否则无穷大.
非单点集:
状态存在dp[i][j]=min(dp[k][s]+w[s][j])
k表示i集合中去掉了j点的集合,s遍历集合k中的点,并且dp[k][s]状态存在,点s到点j有边存在,w[s][j]表示边的权值.状态不存在dp[i][j]为无穷大.

最后的结果是:
min(dp[(1<<n)-1][j])(0≤j＜n)
技巧:利用2进制,使得一个整数表示一个点集,这样集合的操作可以用位运算来实现.例如从集合中去掉点j:
k=i&(~(1<<j))或者
k=i-(1<<j)

遍历点集i中都包含哪些点:
for(j=0;(1<<j)<=i;j++){
if(((1<<j)&i)!=0):
点集i就包含点j
}
把点j加入点集i
i=(i|(i<<j));

例题2

[POJ3254]Corn Fields
题目大意
一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛（不包括斜着的），即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)
输入
1<=n<=12，1<=m<=12
输出
一个mod100000000的整数
样例输入
2 3
1 1 1
0 1 0
样例输出
9
分析:
从题意我们可以知道牛与牛之间不能相邻，我们可以很容易的想到可以一行一行的递推，因为每只牛能不能放只与上一行和当前这一行有关。
所以dp中有一个维度是用来表示第几行的，还有一个维度就是用来表示哪一行的状态的。
假设有m列，则状态最多只有（1<<m-1）种，这是显然的。因为他每一列只有放和不放这两种决策。
那么怎么表示状态是个关键问题，这就要用到状态压缩了，用二进制来表示某个状态，比如
0101代表的就是1、3列不放牛，2、4列放牛。这样不仅省空间省代码还省时间。
要用位运算是必须的。

参考代码：

#include <cstdio>  
#include <cstring>  
const int N = 13;  
const int M = 1<<N;  
const int mod = 100000000;  
int st[M],map[M];  ///分别存每一行的状态和给出地的状态  
int dp[N][M];  //表示在第i行状态为j时候可以放牛的种数  
bool judge1(int x)  //判断二进制有没有相邻的1  
{  
    return (x&(x<<1));  
}  
bool judge2(int i,int x)  
{  
    return (map[i]&st[x]);  
}  
int main()  
{  
    int n,m,x;  
    while(~scanf("%d%d",&n,&m))  
    {  
        memset(st,0,sizeof(st));   //初始化
        memset(map,0,sizeof(map));  //初始化
        memset(dp,0,sizeof(dp));  //初始化
        for(int i=1;i<=n;i++)  
        {  
            for(int j=1;j<=m;j++){  
                scanf("%d",&x);  
                if(x==0)  
                    map[i]+=(1<<(j-1));  //获得每行的值(十进制)
            }  

        }  
        int k=0;  
        for(int i=0;i<(1<<m);i++){  //遍历所有的行情况,选出可行的行情况的状态
            if(!judge1(i))  
                st[k++]=i;  
        }  
        for(int i=0;i<k;i++)  
        {  
            if(!judge2(1,i))  //所有可行的行情况中，与第一行的值求交
                dp[1][i]=1;  //表示第1行第i种行情况的可能性
        }  
        for(int i=2;i<=n;i++)  //表示行
        {  
            for(int j=0;j<k;j++)  //表示记录的可行
            {  
                if(judge2(i,j))  //判断第i行 假如按状态j放牛的话行不行。  
                    continue;  
                for(int f=0;f<k;f++)  
                {  
                    if(judge2(i-1,f))   //剪枝 判断上一行与其状态是否满足  
                        continue;  
                    if(!(st[j]&st[f]))  
                        dp[i][j]+=dp[i-1][f];  
                }  
            }  
        }  
        int ans=0;  
        for(int i=0;i<k;i++){  
            ans+=dp[n][i];  
            ans%=mod;  
        }  
        printf("%d\n",ans);  
    }  
    return 0;  
}

1…n个树枝拿掉几个树枝使不能形成三角形

动态规划表

两种表法:填表法和刷表法
填表法:就是一般的动态规划,当前点的状态,可以直接用状态方程,根据之前的状态推导出来
刷表法:由当前点的状态,更新其他点的状态,需要注意:只用当每个状态所依赖的状态对它的影响相互独立

通过例题看刷表

题意：三个数，T表示最大的饱腹值，A表示吃a可以增加的饱腹值，B表示吃b可以增加的饱腹值。ab都有无穷多个。初始状态是0，可以有一次通过喝水，来使饱腹值减少一半（向下取整）的机会。

分析：首先按照一般的动态规划，会有问题。
为什么不能用填表法？
因为当前状态既与之前的状态有关，又与之后的状态有关。当前的状态与dp[ i - a],dp[i - b],dp[i * 2]有关。所以用刷表法，来直接更新状态。
此题中，喝水后的状态可以在喝水的基础上计算。及可以先计算所有喝水前的状态，再计算所有喝水后的状态。喝水前的状态可以更新喝水后的状态。
另：注意，本题中饱腹值不能超过最大值T

前缀树

有序表

DP

尝试->dp(高度结构化的表)

如果结构化数据难以实现,考虑用一个缓存记忆,已经出现过的状况。

例题StickersToSpellWord
动态规划核心是减少重复计算

动态规划——乘法表问题

本体和矩阵相乘问题非常i相似
问题:

依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。

例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。

试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。
输入:
输入一个以a,b,c组成的任意的一个字符串str
输出:
计算出的加括号方式数
分析:
乘法表问题直观理解就是通过加括号使得最终运算结果为a，该问题与矩阵连乘问题类似，矩阵连乘是每一次加括号选择运算量最小的，写成数学表达式有：

而乘法表问题则是计算所有加括号运算结果为a的情况数，并不要求输出加括号方式。那么可以从乘法的最小单元两个符号相乘的所有可能开始，接着在两个符号相乘的基础上计算三个符号相乘的所有可能。直到计算N长度的符号1-N的所有可能。可以定义一个三维数组 result[n][n][3],n为输入字符串的长度， result[i][j][0]为从字符串中第i个元素到第j个元素的子串表达式值为a的加括号方式数， result[i][j][1]为从字符串中第i个元素到第j个元素的子串表达式值为b的加括号方式数，result[i][j][2]为从字符串中第i个元素到第j个元素的子串表达式值为c的加括号方式数。
设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。
设字符串的第 i 到第 j 位乘积为 a 的加括号法有 result[i][j][a] 种，
字符串的第 i 到第 j 位乘积为 b 的加括号法有 result[i][j][b] 种,
字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。
则原问题的解是： result[1][n][a] 。

设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：

1
2
3

result[i][j][a] += result[i][k][a]*result[k+1][j][c]+result[i][k][b]*result[k+1][j][c]+result[i][k][c]*result[k + 1][j][a];
result[i][j][b] += result[i][k][a]*result[k+1][j][a]+result[i][k][a]*result[k+1][j][b]+result[i][k][b]*result[k + 1][j][b];
result[i][j][c] += result[i][k][b]*result[k+1][j][a]+result[i][k][c]*result[k+1][j][b]+result[i][k][c]*result[k + 1][j][c];

maxn=50
result=np.zeros((maxn,maxn,3))
def getNum(str):
  for i in range(1,len(str)+1):
    if(str[i-1]=='a'):
      result[i][i][0]=1
    else:
      result[i][i][0]=0
    if(str[i-1]=='b'):
      result[i][i][1]=1
    else:
      result[i][i][1]=0
    if(str[i-1]=='c'):
      result[i][i][2]=1
    else:
      result[i][i][2]=0
  for r in range(2,len(str)+1):
    for i in range(1,len(str)+1-r):
      j=i+r-1
      for k in range(i,j+1):
        result[i][j][0]+=result[i][k][0]*result[k+1][j][2]+result[i][k][1]*result[k+1][j][2]+result[i][k][2]*result[k+1][j][0]
        result[i][j][1]+=result[i][k][0]*result[k+1][j][0]+result[i][k][0]*result[k+1][j][1]+result[i][k][1]*result[k+1][j][1]
        result[i][j][2]+=result[i][k][1]*result[k+1][j][0]+result[i][k][2]*result[k+1][j][1]+result[i][k][2]*result[k+1][j][2]

  return result[1][len(str)][0]

二叉树递归套路

第六课讲义题二、题三

二叉树递归与非递归遍历

二叉树是一种非常重要的数据结构，很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式，因为树的本身就是用递归定义的，因此采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的）。下面先简要介绍三种遍历方式的递归实现，再详细介绍三种遍历方式的非递归实现。

遍历的递归实现

先序遍历——按照“根节点-左孩子-右孩子”的顺序进行访问。

def pre_traverse(head):
  if(head):
    print(head.value)
    if(head.left):
      pre_traverse(head.left)
    if(head.right):
      pre_traverse(head.right)

中序遍历——按照“左孩子-根节点-右孩子”的顺序进行访问。

def in_traverse(head):
  if(head):
    if(head.left):
      in_traverse(head.left)
    print(head.value)
    if(head.right):
      in_traverse(head.right)

后序遍历——按照“左孩子-右孩子-根节点”的顺序进行访问。

def beh_traverse(head):
  if(head):
    if(head.left):
      beh_traverse(head.left)
    if(head.right):
      beh_traverse(head.right)
    print(head.value)

遍历的非递归实现

前序遍历的非递归实现
对于任一节点P，
1）输出节点P，然后将其入栈，再看P的左孩子是否为空；
2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；
3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4）若不为空，则循环至1）操作；
5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；
6）直到当前节点P为NULL并且栈空，遍历结束。

def pre_traverse(head):
  stack=[]
  curnode=head
  while(curnode!=None||len(stack)!=0):
    print(curnode.value)
    stack.append(curnode)
    curnode=curnode.left
    while(curnode==None and len(stack)!=0):
      curnode=stack.pop()
      curnode=curnode.right

另一种思路:

def preOrder(head):
  if(head==None):
    return
  stack=[]
  curnode=head
  while(curnode!=None):
    print(curnode.value)
    if(curnode.right!=None):
      stack.append(curnode.right)
    if(curnode.left!=None):
      stack.append(curnode.left)
    else:
      if(len(stack)==0):
        break
      curnode=stack.pop()

中序遍历的非递归实现
根据中序遍历的顺序，先访问左子树，再访问根节点，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的中序遍历顺序为：DBEAFC。非递归的实现思路如下：

对于任一节点P，
1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3）若不为空，则重复1）和2）的操作；
4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
5）直到当前节点P为NULL并且栈为空，则遍历结束。

def in_traverse(head):
  stack=[]
  curnode=head
  while(curnode!=None):
    if(curnode.left!=None):
      stack.append(curnode.left)
      curnode=curnode.left
    else:
      print(curnode.value)
      curnode=curnode.right
      while(curnode!=None and len(stack)!=0):
        curnode=stack.pop()
        print(curnode.value)
        curnode=curnode.right

另一种思路:

def InOrder(head):
  if(head==None):
    return
  stack=[]
  curnode=head
  do
  {
    while(curnode!=None):
      stack.append(curnode)
      curnode=curnode.left
    if(len(stack)!=0):
      curnode=stack.pop()
      print(curnode.value)
      curnode=curnode.fight
  }while(curnode!=None or len(stack)!=0)

后序遍历的非递归实现
根据后序遍历的顺序，先访问左子树，再访问右子树，后访问根节点，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的后序遍历顺序为：DEBFCA。后序遍历的非递归的实现相对来说要难一些，要保证根节点在左子树和右子树被访问后才能访问，思路如下：

对于任一节点P，
1）先将节点P入栈；
2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
4）直到栈空，遍历结束。

def beh_traverse(head):
  stack=[]
  curnode=head
  prenode=None
  stack.append(curnode)
  while(len(stack)!=0):
    curnode=stack.pop()
    if((curnode.left!=None and curnode.right!=None) or (prenode!=None) and(curnode.right==prenode or curnode.right==prenode)):
      print(curnode.value)
      stackout=stack.pop()
      prenode=curnode
    else:
      if(curnode.right!=None):
        stack.append(curnode.right)
      if(curnode.left!=None):
        stack.append(curnode.left)

根据中序遍历和先序遍历直接写出后序遍历

贪心法

用来简化转移方程.
贪心算法是什么意思？举个例子：现有一个能装4斤苹果的袋子,苹果有两种,一种3斤一个,一种2斤一个,怎么装才能得到最多苹果?如果拿两个2斤的苹果,就刚好装满了,但是如果按贪心算法拿的话,首先就要把最重的苹果拿下(要符合贪心两字),但并没有得到最多苹果.
贪心算法保证了局部最优,但并不能保证得到最优解
什么时候用贪心法?满足两个条件：

具有最优子结构
贪心选择

如果用动态规划做的话思想是这样的,假设我们已经知道第k个活动是活动序列之一,那么又把1到k和k到11看作两个子问题继续分
用贪心法的话思想很简单,活动越早结束,剩下的时间是不是越多?那我就找最早结束的那个活动,找到后在剩下的活动中再找最早结束的不就得了
虽然贪心算法的思想简单,但是贪心法不保证能得到的问题的最优解,ru过得不到最优解,那就不是我们想要的东西了,所以我们需证明的是在这个问题中,用贪心法能得到最优解

先要证明的是:
S是所有活动的集合,令m为活动集中最早结束的活动,则m在A活动序列中(A就是我们要求出的那个活动序列)
证明:设j为A中最早结束的活动,如果m=j,那么就证明了最早结束活动m在A中,如果m!=j,那么我们把j从A中剔除掉,然后换上m,依然能得到一个最优活动序列(m是所有活动中最早结束的),所以贪心法在这个问题里能得到最优解.

s=[0,1,3,0,5,3,5,6,8,8,2,12]#增加了第0个活动，活动开始时间
f=[0,4,5,6,7,9,9,0,10,11,12,14,16]#活动结束时间

def RAS(s,f,k,n):
  m=k+1
  while(m<=n and s[m]<f(k)):
    m=m+1
  if(m<=n):
    return str(m)+","+RAS(s,f,m,n)
  else:
    return null

0-1背包问题

0-1背包的例子:

1
2
3

weight=[2,2,6,5,4]
value=[3,6,5,4,6]
weight_most=10

有5个物体，考虑装入背包，背包的总承重是10。第一个物体重2，价值是3，如此类推。那么怎样才能在不超过背包承重的范围下，使得背包装的物体的总价值最高呢？哈哈，先考虑一些简单的情况如果只允许装前1件物体，不，这样还不够简单。
自底向上分析:

最简单是只允许装前0件物体，即什么都不装，那这样的话，管你背包承重0也好，10也好，100也好。那么总价值最高都是0。
好了，难一点点，只允许装前1件物体，也就是只允许装第1件了。那么不要马上跳到承重10，先从承重0开始，如果背包只允许承重0的话，那么总价值最高也是0。|承重1呢，第一件物体重2，装不下，怎么办呢，那就不装呗还能怎么办，瞄一眼前0件（也就是不装）承重1的情况，总价值是0，所以总价值还是0咯。|好了，承重是2呢？2-2=0装得下，装的话比前0件（不装）承重2的总价值要高！那你装不装？肯定要装，那么总价值最高就是3。|那么承重是3呢？3-2=1，还有1的重量可以装，卧槽，可是装不了，因为，只允许装前一件，如果换个说法的话，就是在承重1的情况下允许装前0件（哈哈，就是不给装嘛）。那么不用看之后承重是5也好，10也好，总价值最高就是3。
只允许装前1件还是很简单的，那么好戏来了！！！允许装前两件呢？承重0，总价值最高0，不用看。|承重1呢，装不下，看前1件（不装）承重1是0，那么前2件承重1是0。|承重2呢，关键了！允许装前2件，两件都装得下，那比较一下吧，是允许装前1件承重2总价值比较高呢？还是？对，还是什么？还是我新允许的第2件价值比较高呢，怎么比较规范表达呢？因为这件是装得下，2-2=0，那么装完之后呢？是不是回归到允许前1件承重0的情况了？很好，那么加上这种情况的总价值最高为0，0+6>3，所以前2件承重2总价值最高就是6了。前2件承重3也差不多。|承重4呢？是前1件承重4总价值为3比较高呢？还是装了第二件之后，回归到前1件承重2，加起来，3+6=9比较高呢？那么就是9！|前5件，承重10咧？
回到我们的总问题，emmmmm，你应该心里有b数了。不就3种情况嘛，承重0或者允许装前0件，全是总价值最高0;如果新允许的第i件装的那件装不下，那就看允许的前i-1件对应的承重的总价值最高咯；如果装得下，那么就要比较允许装前i-1件对应的承重的总价值最高和这承重减去新装的那件，回归到那种情况的总价值最高相加。没了，就三种情况，状态转移方程就这样出来了。

$bag[i,j]= \begin{cases} 0 \ \ \ \ i=0\ \ or \ \ j=0\\ bag[i-1,j] \ \ \ weight[i]>j\\ max(bag[i-1,j],bag[i-1,j-weight[i]]+value[i]) \ \ weight[i]<=j\\ \end{cases}$


import numpy as np

weight=[2,2,6,5,4]
value=[3,6,5,4,6]
weight_most=10
def bag_0_1(weight,value,weight_most):#return max value
    num = len(weight)
    weight.insert(0,0)#前0件要用
    value.insert(0,0)#前0件要用
    bag=np.zeros((num+1,weight_most+1),dtype=np.int32)#下标从零开始
    for i in range(1,num+1):
        for j in range(1,weight_most+1):
            if weight[i]<=j:
                bag[i][j]=max(bag[i-1][j-weight[i]]+value[i],bag[i-1][j])
            else:
                bag[i][j]=bag[i-1][j]
    # print(bag)
    return bag[-1,-1]

result=bag_0_1(weight,value,weight_most)
print(result)

贪心法与动态规划

最优解问题大部分都可以拆分成一个个的子问题,把解空间的遍历视为对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,大部分情况下这是不可行的.贪心算法和动态规划本质上是对子问题树的一种修建,两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优解)。动态规划方法代表了这一类问题的一般解法,我们自底向上构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其他的值舍弃.而贪心算法是动态规划方法的一个特例,可以证明每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况.换句话说,不需要直到一个节点所有子树的情况,就可以求出这个节点的值.由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了.

子数组最大累加和

假设答案法

LeetCode 754. Reach a Number

Problem:

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:
Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.
Example 2:
Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step from 1 to -1.
On the third move we step from -1 to 2.

分析：
要考虑最短的步数,显然,+的越多,步数最少.
考虑一直加,直到到达某一步k时超过了target,此时的pos离target的距离为d.想办法修正这个d为0.如果我们更改已知的步长,会使总长度减少2倍的该步长,所以对任意d为偶数时,该方法不需要新增步数.如果d是奇数时,肯定不能用当前步数到达,也不可能减少1步数到达,因此需要增加1步数,这个步数加上后d也会发生变化,如果d还是奇数则继续加步数,毕竟不能连续两个数都是偶数,如果d是偶数则停止增加步数.

class Solution {
public:
    int reachNumber(int target) {
        target = std::abs(target);
        int k = 0;
        int sum = 0;
        while (sum < target) sum += (++k);
        const int d = sum - target;
        if (d % 2 == 0) return k;
        return k + 1 + (k % 2);
    }
};

笔试刷题（三）