作者：小 琛
欢迎转载，请标明出处
引言：动态规划是算法中较难的内容，常常被用来区分学习者的档次，笔者也是在面试中发现了这个问题，故而回头认真学习并总结递归算法，希望能够帮助到阅读的你
“世界上的所有问题，都可以化繁为简，化简为空”。这种思想本身就是一门艺术，就像写代码的我们，同样在做一门艺术。
1. 动归从某种意义讲其实就是递归的优化
以前我们接触过一种思想：递归。一个大问题可以拆分为若干个小问题，而小问题最后变为了一个确定的、简单的问题。动态规划的思路本身就和递归类似：当遇到一个问题时，这个问题的解决是有规律可循的，可将该问题拆分为多个小问题来解决，例如斐波那契数列中，F(n)的求解等于F(n-1)+F(n-2)。而当我们确定了这些规律后，动态规划所做的操作，就是将这类规律总结，形成一个动态转移方程，例如上面的斐波那契数列的F(n)=F(n-1)+F(n-2)本质就是一个动态转移方程。
2. 动归对于递归最大的优化就是用记录法代替栈帧的开销
C++学习者肯定明白，递归的过程就是函数栈帧的开辟，当递归次数增大而导致程序崩溃时，就是因为过多的栈帧导致的栈溢出。而动态规划常用的办法，定义数组dp(该数组需要根据需求设定，可能是一维，也可能二维)，dp用来记录每一个状态，从而实现求解下一个状态的时候直接从之前的状态获得即可。
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
题目分析：斐波那契数列常用来学习循环或递归，此处我们用动态规划思路解决。
class Solution {
public:
int fib(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
vector<int> dp(n+1,0);
dp[1]=1;
for (int i=2;i<n+1;i++)
{
dp[i]=(dp[i-1]+dp[i-2])%1000000007;
}
return dp[n];
}
};
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，也可以跳n级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
解题思路：这道题其实是一道经典的递归问题，而此处我们用动态规划来解答。仍然按照常规步骤：
#include <iostream>
#include <vector>
class Solution {
public:
int numWays(int n)
{
vector<int> dp(n+1,0);
dp[0]=1;
for (int i=1;i<=n;i++)
{
dp[i]=2*dp[i-1];
}
return dp[n];
}
};
前面谈到，动态规划的核心，在于问题的确定、转移方程的列写、初始值的确定、记录数组的定义。当分析的问题难度提升，则前三步有难度时，动态规划题目级别就上升了，此时则需要认真分析，核心点还是在于抓住动态规划的解决步骤，将困难的问题简单化
题目：
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
题目解答
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> myset;
for (auto str: wordDict)
{
myset.insert(str);
}
vector<bool> dp(s.size()+1);
dp[0]=true;
for (int i=1;i<dp.size()+1;i++)
{
for(int j=0;j<i;j++)
{
if (dp[j] && myset.find(s.substr(j,i-j))!=myset.end())
{
dp[i]=true;
break;
}
}
}
return dp[s.size()];
}
总结：该题目的难点在于最初的分析，很多时候无法和动态规划连接在一起，因此在遇到这类题目的时候，可以多举几个例子，查看分析当前的判断和之前的判断有何种联系，得到这种递推式的关系后，再列写状态转移方程。同时需要将之前学习过的知识联系起来，方可解答。
j
题目分析：
该题是一道经典的动归题目。分析采用常规流程即可
int minimumTotal(vector<vector<int>>& triangle) {
int n=triangle.size();
vector<vector<int>> dp(n,vector<int>(n));
dp[0][0]=triangle[0][0];
int i,j;
for ( i=1;i<n;i++)
{
dp[i][0]=dp[i-1][0]+triangle[i][0];
for ( j=1;j<i;j++)
{
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
}
dp[i][i]=dp[i-1][j-1]+triangle[i][j];
}
return *min_element(dp[n-1].begin(),dp[n-1].end());
}