【剑指offer】礼物的最大价值（python）

使用动态规划求解，DFS过于复杂，不是最优解。
每次都求到达相邻的两个列中的最大值。

# -*- coding:utf-8 -*-

class Bonus:
    def getMost(self, board):
        # write code here
        if not board or len(board) == 0 or len(board[0])==0:
            return 0
        n = len(board[0])
        dp = [0 for i in range(n)]
        for value in board:
            dp[0] += value[0]
            for j in range(1,n):
                dp[j] = max(dp[j], dp[j-1])+value[j]
        return dp[n-1]

大神的java代码：

import java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
       int[] dp = new int[board.length+1];
       for(int i=1;i<dp.length;i++){
          for(int j=1;j<dp.length;j++){
              dp[j] = Math.max(dp[j], dp[j-1])+board[i-1][j-1];
          }
       }
       return dp[dp.length-1];

    }
}

【剑指offer】最长不含重复字符的子字符串

题目：输入一个字符串(a~z)，求其最长不含重复字符的子字符串长度。

小于j-i，说明字符s[i]在子字符串dp[j-1]区间之外，大于等于j-i，说明字符在子字符串区间之中，则 dp[j]的左边界由s[i] 决定，即 dp[j] = j - i.

1. python字符串定位，s[loc]
2. python字符串长度，len(s)
3. pythonASCII码和字符互换，
   print( c + " 的ASCII 码为", ord(c))
   print( a , " 对应的字符为", chr(a))
4. python判断字符串为空 s.isspace()
5. ASCII码一共128个
6. 使用辅助数组preIndexs作为哈希表统计各字符最后一次出现的索引位置，遍历到s[j]时通过哈希表得到最近的相同的字符位置preI

   class Solution(object):
     def lengthOfLongestSubstring(self, s):
         """
         :type s: str
         :rtype: int
         """
         if s.isspace(): return 1
         curlen = 0
         maxlen = 0
         preIndexs = [-1 for i in range(128)]
         for curI in range(len(s)):
             c = ord(s[curI]) - ord('a')
             preI = preIndexs[c]
             if preI == -1 or curI - preI > curlen:
                 curlen += 1
             else:
                 maxlen = max(maxlen, curlen)
                 curlen = curI - preI
             preIndexs[c] = curI
         maxlen = max(maxlen, curlen)
         return maxlen