mxn棋盘格每一格上的数字可正可负，从左上角出发选择向右或向下两个方向到达右下角，要求x与路径和的和是正数，问x的初始最小值。动态规划，从右下方往左上角推，构造dp[n+1]={INT_MAX},dp[n-1]=1,dp[n]=1，走完右下角至少和为1，for(int i=m-1;i>=0;i--){for(int j=n-1;j>=0;j--){int tmp=min(dp[j],dp[j+1]);dp[j]=max(tmp-board[i][j],1);}dp[n]=INT_MAX;}return dp[0];找右方和下方方格的最小值，dp[j]=max(tmp-board[i][j],1)保证对0<=i<n，dp[i]>=1，tmp-board[i][j]推算满足路径和为正数条件进入[i,j]方格前的路径和，如果tmp-board[i][j]>1，则dp[j]至少得是tmp-board[i][j]，比1大，要不后面的方格走下去路径和会小于0,tmp的选择标准是右和下的最小值，有一条最小的路径和满足题意即可，m-1号行之前dp[n]=INT_MAX是因为对0<=i<m-1，board[i][n-1]只能向下，不能向右，之前设dp[n]=dp[n-1]=1是在board[m-1][n-1]走完的路径和有个好接手的地方（向右或向下），用在找tmp好形式统一地计算。
nxn网格上每一格有个数：1表示有个樱桃，可以摘且能通过，-1表示有荆棘，无法通过，0表示可以通过，问从左上角出发走过一段路遇到1,摘一个樱桃，网格从1变为0,无法通过-1的格，到达右下角（或走不到），再从右下角走回左上角（如果无法到达右下角，则无法实现），问这个过程中能摘到的最大樱桃树。[2]可以当作a和b同时从左上角往右下角向右或向下走，则a和b能摘到的樱桃最大总和。dp[x][y][s]表示第s步a横坐标为x而b横坐标为y时能摘到的的最大樱桃总和，结果应为dp[n-1][n-1][2n-2]。dp元素赋初值INT_MIN，dp[0][0][0]=grid[0][0]，初始a和b都在左上角，能摘到的樱桃树是grid[0][0](grid[0][0]不会取-1)，a和b从左上角到达右下角（如果能到达的话）总共要走2n-2步，第k+1步时a横坐标为x,b横坐标为y,a纵座标为k+1-x,b纵座标为k+1-y,a和b的横纵座标需要在合理范围内，且a和b所在的格子不能取-1,以此讨论a和b在k+1步时可能位置，相比第k步a和b的可能位置，多摘了grid[x][k+1-x]+grid[y][k+1-y](x!=y)或grid[x][k+1-x](x==y)个樱桃，而第k步a和b的可能位置dp[x][y][k]、dp[x-1][y][k]、dp[x][y-1][k]和dp[x-1][y-1][k]中a和b的位置经过一步向下或向右的操作到达dp[x][y][k+1]，寻找dp[x][y][k+1]的潜在最大值，最后返回max(0,dp[n-1][n-1][2n-2])
a和b轮流从数组的头或尾不放回地取出一个数，数取完后取到的数的和最大的一方获胜，问在最优策略下a能否取胜，如果平局则判a胜[3]。二维dp,dp[n][n]，dp[i][j]表示当数组为nums[i:j+1]时最优策略下当前取的人比下一个取数的人最后取完、数的和多多少，dp[i][i]=nums[i]，因为下一个人取数的和是0,当前的人取数的和是nums[i]，i从n-2到0,j从i+1到n-1，关于遍历流程为何如此写，见走向新时代第37行的分析，dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])，当前只能取头或尾，nums[i]、nums[j]，取完后，下一个人要面对dp[i+1][j]或dp[i][j-1]，但这个差距从下一个人的角度算的，故减，最后dp[0][n-1]大于等于0,则a赢。空间复杂度从O(n^2)到O(n)的优化：动规主函数，dp[j]=max(nums[i]-dp[j],nums[j]-dp[j-1])，dp[j]初始值为nums[j]。
参考链接：[1].174. 地下城游戏
[2].741. 摘樱桃
[3].486. 预测赢家