写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
public void fib(){
int n = 45;
int l = 1, r = 0, tar = 0;
//l代表F(N - 1)，r代表F(N - 2)
for (int i = 2; i <= n; i++) { //前两个已知无需计算
tar = (l + r)%1000000007;
r = l;
l = tar;
System.out.println(tar);
}
}给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
public void lengthOfLIS() {
int[] nums = new int[]{10,9,2,5,3,7,101,18};
int[] dp = new int[nums.length];
//dp代表以i为结尾的最长子序列长度
int max = 1;
//备忘录 记录最大值
Arrays.fill(dp,1);
//初始化为1，每个最长子序列最小为1
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i ; j++) {
if (nums[i] > nums[j]){
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
max = Math.max(max, dp[i]);
}
}
System.out.println(max);
} 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
思路：其实很简单，就是dp表示的是以i和j为结尾的序列的最大公共子序列的长度
知识点
1、思路问题：动态规划也是有套路的：单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。
2、边界问题：动态规划dp经常需要定义为n+1和m+1 这个题浪费的全部时间都在于这个边界不明确
3、base问题：这个的base 是当text1和text2为空指针的时候的最大公共子序列的长度，那么一定为0
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
//dp记录的是以i为结尾和以j为结尾的序列的最大公共子序列的长度
// for (int i = 0; i < text1.length(); i++) {
// System.out.println(i);
// Arrays.fill(dp[i], 0);
// }
//完全没有必要,因为数组的默认值为0
int max = 0;
//记录最大值
//下面全部是在浪费时间,只需要把数组定义为+1就行了
// for (int i = 0; i < text1.length(); i++) {
// if (text1.charAt(i) == text2.charAt(0)){
// if (i > 0 && dp[i-1][0] == 1){
// dp[i][0] = 1;
//
// }
// else {
// dp[i][0] = 1;
// }
// }
// else {
// if (i > 0) dp[i][0] = dp[i-1][0];
// }
// max = Math.max(max, dp[i][0]);
// }
// for (int j = 0; j < text2.length(); j++) {
// if (text1.charAt(0) == text2.charAt(j)){
// if(j > 0 && dp[0][j-1] == 1){
// dp[0][j] = 1;
// }
// else {
// dp[0][j] = 1;
// }
// }
// else {
// if (j > 0) dp[0][j] = dp[0][j-1];
// }
// max = Math.max(dp[0][j], max);
// }
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)){
dp[i][j] = dp[i-1][j-1] + 1;
//这里不需要取[i-1][j] 和 [i][j-1]，因为在不相同的时候已经比较过了，所以直接全部往前一个指针就行了
}
else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
System.out.println("i:"+i+",j:"+j+",dp:"+dp[i][j]);
max = Math.max(dp[i][j], max);
}
}
System.out.println(max);
}背包九讲：https://blog.csdn.net/yandaoqiusheng/article/details/84782655/
正序逆序问题 https://blog.csdn.net/yandaoqiusheng/article/details/84929357
https://www.acwing.com/problem/content/2/
二维数组
import java.util.Scanner;
public class Pack01 {
public static void main(String[] args) {
int N = 1001;
int n, m;
//总个数和总体积
int[] v = new int[N];//每个的体积
int[] w = new int[N];//每个的价值
int[][] dp = new int[N][N];//代表的是前i件物品放入剩余容量为j的背包中的最大价值
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int best = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (j < v[i]){ //第一个选择，如果容量不够vi
dp[i][j] = dp[i-1][j];
}else {
dp[i][j] = Math.max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);//第二个选择，如果够vi，vi放不放
}
// System.out.println(dp[i][j]);
best = Math.max(best, dp[i][j]);
}
}
System.out.println(best);
}
}一维数组
主要思路要转过来弯
https://blog.csdn.net/weixin_41061962/article/details/80319436 讲的非常好。
数组中保存的是外循环中i-1次的值，还未更新，所以max中的两个值都代表的dp[i-1]
public static void main(String[] args) {
int N = 1001;
int n, m;
//总个数和总体积
int[] v = new int[N];//每个的体积
int[] w = new int[N];//每个的价值
int[] dp = new int[N];//代表的是前i件物品放入剩余容量为j的背包中的最大价值
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int best = 0;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) { //这里是个优化，j必须要在大于V[i]的前提下进行循环
dp[j] = Math.max(dp[j-v[i]]+w[i],dp[j]);//第二个选择，如果够vi，vi放不放
// 代表的是dp[i][j] 代表的是dp[i-1][j]
// 原因：现在数组中保存的是外循环中i-1次的值，还未更新，所以max中的两个值都代表的dp[i-1]
best = Math.max(best, dp[j]);
}
}
System.out.println(best);
}
}方法1：当做0,1背包问题进行理解，区别在于是否能够增加k个i
//换成01背包问题
public static void main(String[] args) {
int N = 1001;
int n, m;
//总个数和总体积
int[] v = new int[N];//每个的体积
int[] w = new int[N];//每个的价值
int[] dp = new int[N];//代表的是剩余容量为j的背包中的最大价值
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int best = 0;
for (int i = 1; i <= n ; i++) {
for (int j = m; j >= v[i] ; j--) {
for (int k = 0; k*v[i] <= j; k++) { // 可以增加多个i
dp[j] = Math.max(dp[j - k* v[i]] + k * w[i], dp[j]);
best = Math.max(best, dp[j]);
}
}
}
System.out.println(best);
}方法2：正统做法
理解：当外循环为i时，内循环正序可以多次添加当前i的物品
public class WanquanPack {
public static void main(String[] args) {
int N = 1001;
int n, m;
//总个数和总体积
int[] v = new int[N];//每个的体积
int[] w = new int[N];//每个的价值
int[] dp = new int[N];//代表的是剩余容量为j的背包中的最大价值
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int best = 0;
for (int i = 1; i <= n ; i++) {
for (int j = v[i]; j <= m ; j++) {
dp[j] = Math.max(dp[j - v[i]] + w[i], dp[j]);
best = Math.max(best, dp[j]);
}
}
System.out.println(best);
}
}方法1：转化成为完全背包中的01背包问题即可。
public class Main {
//换成01背包问题
public static void main(String[] args) {
int N = 1001;
int n, m;
//总个数和总体积
int[] v = new int[N];//每个的体积
int[] w = new int[N];//每个的价值
int[] s = new int[N];//每个的个数
int[] dp = new int[N];//代表的是剩余容量为j的背包中的最大价值
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
s[i] = scanner.nextInt();
}
int best = 0;
for (int i = 1; i <= n ; i++) {
for (int j = m; j >= v[i] ; j--) {
for (int k = 0; k <= s[i] && k * v[i] <= j; k++) { //这里就s
dp[j] = Math.max(dp[j - k* v[i]] + k * w[i], dp[j]);
best = Math.max(best, dp[j]);
}
}
}
System.out.println(best);
}方法2：对于整数s，k = ceil（log2（s））, 2^0 2^1....2^k 可以表示小于等于s的任何数。
所以可以将物品分为2^0 2^1....2^k个，重量也分别为w*2^0 w*2^1... w*2^k
public class DuochongBeibao {
public static void main(String[] args) {
int N = 1001;
int n, m;
int[] dp = new int[N];//代表的是剩余容量为j的背包中的最大价值
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
ArrayList<Good> goods = new ArrayList<>(); //数组存储分类之后的物品
for (int i = 1; i <= n; i++) {
int v = scanner.nextInt();
int w = scanner.nextInt();
int s = scanner.nextInt(); //代表物品原个数
for (int k = 1; k <= s ; k *= 2) { //k代表物品分类的个数 每次*2
s -= k;//s减去已经分类之后的物品数量
goods.add(new Good(v * k, w * k));
}
if (s > 0) goods.add(new Good(v * s, w * s));//如果还有剩余，继续添加到数组中
}
int best = 0;
//此时就完全转化为0，1背包问题
for (Good good: goods) {
for (int j = m; j >= good.v ; j--){
dp[j] = Math.max(dp[j - good.v] + good.w, dp[j]);
best = Math.max(best, dp[j]);
}
}
System.out.println(best);
}
}
class Good{
int v = 0;
int w = 0;
public Good(int v, int w){
this.v = v;
this.w = w;
}
}对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
思路：
dp代表的是走到第i层的方法数
dp[i] = dp[i-1] + dp[i-2]
class Solution {
int res;
public int climbStairs(int n) {
if(n==1) return 1;
int[] dp = new int[n + 1];//代表的是走到第i层的方法数
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
输入：m = 3, n = 7
输出：28
思路：初始化不仅仅是第一个，还需要将上、左两个边上的点进行初始化
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];//i，j坐标有多少方法
//初始化应该上面一排和最左边一排都为1
for(int i = 0; i < m; i++){
dp[i][0] = 1;
}
for(int i = 0; i < n; i++){
dp[0][i] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
思路：有了障碍物，
会影响初始化和动态规划的过程
初始化的时候，左、上的要在障碍物之后都标记为0
过程中，遇到障碍物，该点定为0
其他的不变
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
int tempi = m, tempj = n;; //记录上方和左面的障碍物的点
for(int i = 0; i < m; i++){
if(obstacleGrid[i][0] == 1) {
dp[i][0] = 0;
tempi = i;
}
else if(i > tempi) { //障碍物之后的点初始化全为0
dp[i][0] = 0;
}
else dp[i][0] = 1;
}
for(int i = 0; i < n; i++){
if(obstacleGrid[0][i] == 1){
dp[0][i] = 0;
tempj = i;
}
else if(i > tempj) {
dp[0][i] = 0;
}
else dp[0][i] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}