回文数
public boolean palindromeNumber(int num) { // Write your code here if(num < 0){ return false; } int div = 1; while(num / div >= 10){ div *= 10; } while(num > 0){ if(num / div != num % 10){ return false; } num = (num % div) / 10; div /= 100; } return true; }动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。其背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。
给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。
示例 ：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重复使用字典中的单词。 解题思路这个方法的想法是对于给定的字符串 s 可以被拆分成子问题 s1 和 s2 。如果这些子问题都可以独立地被拆分成符合要求的子问题，那么整个问题 s 也可以满足。也就是，如果 \(catsanddog\) 可以拆分成两个子字符串 "\(catsand\)" 和 "\(dog\)" 。子问题 "\(catsand\)" 可以进一步拆分成 "\(cats\)" 和 "\(and\)" ，这两个独立的部分都是字典的一部分，所以 "\(catsand\)" 满足题意条件，再往前， "\(catsand\)" 和 "\(dog\)" 也分别满足条件，所以整个字符串 "\(catsanddog\)" 也满足条件。
现在，我们考虑 \(dp\) 数组求解的过程:
我们使用 \(n+1\) 大小数组的 \(dp\) ，其中 \(n\) 是给定字符串的长度。
我们也使用 2 个下标指针 \(i\) 和 \(j\) ，其中 \(i\) 是当前字符串从头开始的子字符串\(（s'）\)的长度， \(j\) 是当前子字符串\(（s'）\)的拆分位置，拆分成 \(s'(0,j)\)和 \(s'(j+1,i)\)。
为了求出 \(dp\) 数组，我们初始化 \(dp[0]\) 为 \(true\) ，这是因为空字符串总是字典的一部分。 \(dp\) 数组剩余的元素都初始化为 \(false\) 。
我们用下标 \(i\) 来考虑所有从当前字符串开始的可能的子字符串。对于每一个子字符串，我们通过下标 \(j\) 将它拆分成 s1' 和 s2'（注意 i 现在指向 s2' 的结尾）。
为了将 \(dp[i]\) 数组求出来，我们依次检查每个 \(dp[j]\) 是否为 \(true\) ，也就是子字符串 s1′ 是否满足题目要求。如果满足，我们接下来检查 s2′ 是否在字典中。如果包含，我们接下来检查 s2′ 是否在字典中，如果两个字符串都满足要求，我们让 \(dp[i]\) 为 \(true\) ，否则令其为 \(false\) 。
public boolean wordBreak(String s, List<String> wordDict) { Set<String> wordDictSet=new HashSet(wordDict); boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordDictSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[s.length()]; } 复杂度分析时间复杂度：\(O(n^2)\) 。求出 \(dp\) 数组需要两重循环。
空间复杂度：\(O(n)\)。\(dp\) 数组的长度是 \(n+1\)。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 :
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 解题思路感觉这题类似斐波那契数列。不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。
第 \(i\) 阶可以由以下两种方法得到：
在第 \((i−1)\) 阶后向上爬 1 阶。
在第 \((i−2)\) 阶后向上爬 2 阶。
所以到达第 \(i\) 阶的方法总数就是到第 \((i−1)\) 阶和第 \((i−2)\) 阶的方法数之和。
令 \(dp[i]\) 表示能到达第 \(i\) 阶的方法总数：
\(dp[i]=dp[i-1]+dp[i-2]\)
\(dp[i]=dp[i−1]+dp[i−2]\)