动态规划（Dynamic Programming）是计算机中解决最优化问题的一种方法，具有效率高、速度快的优点。
引入一个经典的动态规划问题：给定一个无序的数组，求出最长的递增子序列的长度。
例如，在 $ nums = [1,5,2,4,3] $ 中，最长子序列为 $ [1,2,3] $，长度为3。
首先采用深搜来解决，代码如下：
public static int dfs(int[] nums, int index) {
int length = 1;
if (index == nums.length - 1) {
return 1;
}
for (int i = index+1; i < nums.length; i ++) {
if (nums[i] > nums[index]) {
length = Math.max(length, dfs(nums, i) + 1);
}
}
return length;
}测试一下：
int[] nums = new int[]{7,8,100,9,54,1,2,21,3,4,88,45,5,6,5,7,89,8,0,9,72,10};
// Ans:1,2,3,5,6,7,8,9,10
int maxLength = dfs(nums, 0);
for (int i = 1; i < nums.length; i ++) {
maxLength = Math.max(maxLength, dfs(nums, i));
}
System.out.println(maxLength);输出10，测试成功。
此时我们把数组的长度设为1000，出现了明显的超时现象。
int[] nums = new int[1000];
for (int i = 0; i < nums.length; i ++) {
nums[i] = (int)(Math.random() * 100);
}不难注意到在深搜的过程中存在大量的重复计算，例如在之前的数组中，在求以 1 开头的最长递增子序列（dfs(nums, 5)）时，我们已经得到了以2开头的最长递增子序列，那么在调用dfs(nums, 6)即对 2 进行深搜时，又对此序列进行了重复的计算，因此我们便可以将已计算好的结果进行一个存储，从而避免重复计算以节省时间成本。
代码如下：
public static int dp(int[] nums) {
int maxLength = 0;
int[] memorization = new int[nums.length];
for (int i = nums.length-1; i >= 0; i --) {
int length = 1;
for (int j = i+1; j < nums.length; j ++) {
if (nums[j] > nums[i]) {
length = Math.max(length, 1+memorization[j]);
}
}
memorization[i] = length;
maxLength = Math.max(maxLength, length);
}
return maxLength;
}例题进阶：找出连续子序列的最大和。
[3, -4,
2,-1,2,6, -5, 4]Ans: 2 - 1 + 2 + 6 = 9
此题我选择的方法是采用二维数组来进行记忆存储：
public static int dp(int[] nums) {
int maxSum = 0;
int[][] memorization = new int[nums.length][nums.length];
for (int i = nums.length-1; i >= 0; i --) {
memorization[i][0] = nums[i];
for (int j = 1; j < nums.length - i; j ++) {
memorization[i][j] = memorization[i][j-1] + nums[i+j];
maxSum = Math.max(maxSum, memorization[i][j]);
}
}
return maxSum;
}例1 台阶问题
题目来源：P1192 台阶问题 - 洛谷
题目描述
有$N$级的台阶，你一开始在底部，每次可以向上迈最多$K$级台阶（最少$1$级），问到达第$N$级台阶有多少种不同方式。
输入格式
两个正整数N，K。
输出格式
一个正整数，为不同方式数，由于答案可能很大，你需要输出$ans \bmod 100003$后的结果。
样例 #1
样例输入 #1
5 2样例输出 #1
8提示
对于$20\%$的数据,有$N ≤ 10, K ≤ 3$;
对于$40\%$的数据，有$N ≤ 1000$;
对于$100\%$的数据，有$N ≤ 100000,K ≤ 100$。
题解
深搜TLE，遂改用DP。
设 $f(x)$ 为到达第 $x$ 级台阶时的方案数。
当 $x\leq k$ 时，$ f(x)=1+f(x-1)+f(x-2)+...+f(1) $；
当 $x>k$ 时，$ f(x)=f(x-1)+f(x-2)+...+f(x-k) $。
解释：
- 当 $x\leq k$ 时，$ f(x)=1（一次上至多k层到x阶）+f(x-1)（在x-1阶上1层）+f(x-2)（在x-2阶上2层）+...+f(1)（在1阶上x-1层） $
- 当 $x>k$ 时，$ f(x)=f(x-1)（在x-1阶上1层）+f(x-2)（在x-2阶上2层）+...+f(x-k)（在x-k阶上k层） $。
代码如下：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int k = keyboard.nextInt();
keyboard.close();
int[] dp = new int[n+1];
dp[0] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= Math.min(i, k); j ++) {
if (j > 0) {
dp[i] += dp[i-j];
dp[i] %= 100003;
}
}
}
System.out.println(dp[n]);
}
}