青蛙跳楼梯

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

  1. // 动态规划实现
  2. func jump(n int) int {
  3.     if n <= 2 {
  4.         return n
  5.     }
  7.     dp := make(map[int]int, n)
  8.     dp[1] = 1
  9.     dp[2] = 2
  10.     for i := 3; i <= n; i++ {
  11.         dp[i] = dp[i-1] + dp[i-2]
  12.     }
  14.     return dp[n]
  15. }
  1. // 递归实现
  2. func jump(n int) int {
  3.     if n <= 2 {
  4.         return n
  5.     }
  6.     return jump1(n-1) + jump1(n-2)
  7. }

机器人

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？

  1. // m是列数,n是行数
  2. func robot(m, n int) int {
  3.     if m <= 0 || n <= 0 {
  4.         return 0
  5.     }
  6.     dp := make([][]int, m)
  7.     a, b := m, n
  8.     for m != 0 {
  9.         m--
  10.         dp[m] = make([]int, n)
  11.         dp[m][0] = 1
  12.     }
  14.     for n != 0 {
  15.         n--
  16.         dp[0][n] = 1
  17.     }
  19.     for i := 1; i < a; i++ {
  20.         for j := 1; j < b; j++ {
  21.             dp[i][j] = dp[i-1][j] + dp[i][j-1]
  22.         }
  23.     }
  24.     return dp[a-1][b-1]
  25. }

回文字符串

  1. func longestPalindrome(s string) string {
  2.     max := 1
  3.     begin := 0
  5.     length := len(s)
  7.     dp := make([][]bool, length,length)
  8.     for i := 0; i < length; i++ {
  9.         dp[i] = make([]bool,length,length)
  10.         dp[i][i] = true
  11.     }
  13.     for j := 1; j < length; j++ { // 遍历行
  14.         for i := 0; i < j; i++ { // 遍历列
  15.             if s[j] != s[i] {
  16.                 dp[i][j] = false
  17.                 continue
  18.             }
  20.             if j-i < 3 { // 字符串就 1 或 2个
  21.                 dp[i][j] = true
  22.             } else {
  23.                 // 保障内部是回文字符串
  24.                 dp[i][j] = dp[i+1][j-1]
  25.             }
  27.             if dp[i][j] && j-i+1 > max {
  28.                 max = j - i + 1
  29.                 begin = i
  30.             }
  31.         }
  32.     }
  33.     return s[begin:begin+max]
  34. }