前言
什么是动态规划算法，简单地说就是不要重复计算已经计算过的内容，而是将其结果存储起来，比如经典的斐波那契数列计算，如下所示。而找到动态规划算法中的核心函数最为重要
public static int fib(int n) {
if (n == 0 || n == 1) {
return 1;
}
int f0 = 1, f1 = 1;
for (int i = 2; i <=n ; ++i) {
int tp = f0 + f1;
f0 = f1;
f1 = tp;
}
return f1;
}
核心函数
f(n) = f(n-1)+f(n-2)
题外话：在动态规划问题中找核心函数，与高中大学寻找数列公式特别相像
示例
在运用动态规划算法时，其中的核心函数返回值并不一定是所求的结果。如示例1
示例1
746. Min Cost Climbing Stairs
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
解题方式：
class Solution {
public int minCostClimbingStairs(int[] cost) {
/*** 记录的并不一定是最终结果 **/
/*** f1,f0 ：记录跳到当前台阶需要的消耗，包含当前台阶 **/
int f0 = cost[0];
int f1 = cost[1];
for (int i = 2; i < cost.length; ++i) {
int tmp = cost[i] + Math.min(f0, f1);
f0 = f1;
f1 = tmp;
}
/*** 判断从哪个台阶上来消耗更少 **/
return Math.min(f0, f1);
}
}
示例2
1025. Divisor Game
***Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of:
Choosing any x with 0 < x < N and N % x == 0.
Replacing the number N on the chalkboard with N - x.
Also, if a player cannot make a move, they lose the game.
Return True if and only if Alice wins the game, assuming both players play optimally.***
在leetcode中这道题目也被归类为DP，当然除了DP以外还有更快的方法，只要你找到规律
DP
这道题目不需要我们太过费心去寻找函数，因为函数已经告诉我们了
class Solution {
public boolean divisorGame(int N) {
Boolean[] a = new Boolean[N+1];
a[1] = false;
for (int i = 2; i <= N; ++i) {
for(int j = i-1; j > 0; --j) {
if (i % j == 0 && !a[i-j]) {
a[i] = true;
break;
} else {
a[i] = false;
}
}
}
return a[N];
}
}
非DP
在寻找DP的核心函数的时候可以发现，奇数最终结果都是false，而偶数的最终结果都是true
class Solution {
public boolean divisorGame(int N) {
if (N == 1) {
return false;
}
return N % 2 == 0;
}
}
小结
其实动态规划很好理解，但是如何运用动态规划需要更深入理解
-大的问题可以分解成小问题的情况一般都可用动态规划算法
-着重找核心函数，而不是问题结果，核心函数找到，问题自然解决
