动态规划

2021-06-10

动态规划

1. 博弈

1.1 Take-Away Games

组合游戏是指一种两个玩家的游戏，每个玩家有相同的信息，不存在随即动作，游戏的结果总是输或者赢。游戏的每个步骤由一个移动构成，通常玩家会交替的进行移动，直到达到终止条件。终止条件是指从该状态不存在任何一个状态移动方式的状态。

这种问题的模板为下：

private boolean canIWin(int n){
    Boolean[] memo = new Boolean[n + 1];//设置memo
    return dfs(n,memo);
}
private boolean dfs(int n,Boolean[] memo){
    if(n < 0) return false;//index边界结束
    if(memo[n] != null) return memo[n];//memo已有结束
    boolean res = false;//initial res
    for (int i = 1;i < 4:i ++){//核心递推公式
        if (n >= i) res |= !dfs(n - i,memo);
    }
    return memo[n] = res;//返回结果并保存到memo
}

例题

LeetCode 292 Nim游戏：

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头。你们轮流进行自己的回合，你作为先手。每一回合，轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者*

题解：

/**
这里保证我能赢的抓取原则是：
dp[i-1],dp[i-2],dp[i-3]都失败了

**/
public boolean canWinNim(int n) {
    Boolean[] memo = new Boolean[n + 1];
    return dfs(n,memo);
}

private boolean dfs(int n,Boolean[] memo){
    if (n < 0) return false;
    if (memo[n] != null) return memo[n];
    boolean res = false;
    for (int i = 1; i < 4; i++) {
        if (n >= i) res |= !dfs(n - i,memo);//只有当res与!dfs都是false的时候才是false
    }
    return memo[n] = res;
}

迭代的方法：

public boolean canWinNim(int n){
    boolean[] dp = new boolean[Math.max(n + 1,4)];
    dp[1] = dp[2] = dp[3] = true;
    for (int i = 4; i <= n; i ++)
        dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i -3];
    return dp[n];
}
/**
终极方案
**/
public boolean canWinNim(int n){
    return n
}

2. 背包问题

01背包问题

问题可以描述为：有n件物品和一个最多只能背重量为w的背包，第i件物品的重量是weight[i]，得到的价值是value[i]，每件物品只能使用一次，求解将哪些物品装入背包里物品的价值总和最大。

使用动态规划的五个步骤来求解：

1.确定dp数组及其下标的含义：

对于背包问题，使用二维数组，即$dp[i][j]$表示从下标为[0-i]的物品任意取，放进容量为j的背包，价值总和最大是多少
2.确定递推公式

可以有两个方向推出来$dp[i][j]$：

（1）当不放物品i：由$dp[i-1][j]$推出，即背包容量为j，里面不放物品i的最大价值，此时$dp[i][j]$就是$dp[i-1][j]$。意思就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值仍然和前面的相同。

（2）当放物品i：由$dp[i-1][j-weight[i]]$推出，$dp[i-1][j-weight[i]]$为背包容量为$j-weight[i]$时不放物品i的最大价值，那么$dp[i - 1][j - weight[i]] + value[i]$，加上的那项式物品i的价值，就是背包放物品i得到的最大的价值。

所以递归的公式是：$ dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])$。
3.dp数组如何初始化

如果背包的容量j为0的话，即$dp[i][0]$，无论取哪些物品，背包的价值总和一定为0。

状态转移方程$ dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])$，可以看出i是由i-1推到出来的，那么i为0的时候要初始化。即存放编号0的物品的时候，各个容量的背包所能够存放的最大价值。

当$j<weight[0]$的时候应该是0，因为背包容量比编号0的物品的重量还小。当$j>=weight[0]$时，$dp[0][j]$应该是$value[0]$，因为背包容量足够放编号0的物品。
1
2
3
4
5
6
7
for (int j = 0 ; j < weight[0]; j++) {
dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
而其他地方的值可以被任意初始化，因为都会被覆盖掉。

.4.确定遍历顺序

这里先遍历物品更好理解

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

5.完整代码

public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagsize = 4;
    testweightbagproblem(weight, value, bagsize);
}
  
public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
    int wlen = weight.length, value0 = 0;
    //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
    int[][] dp = new int[wlen + 1][bagsize + 1];
    //初始化：背包容量为0时，能获得的价值都为0
    for (int i = 0; i <= wlen; i++){
        dp[i][0] = value0;
    }
    //遍历顺序：先遍历物品，再遍历背包容量
    for (int i = 1; i <= wlen; i++){
        for (int j = 1; j <= bagsize; j++){
            if (j < weight[i - 1]){
                dp[i][j] = dp[i - 1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            }
        }
    }
    //打印dp数组
    for (int i = 0; i <= wlen; i++){
        for (int j = 0; j <= bagsize; j++){
            System.out.print(dp[i][j] + " ");
        }
        System.out.print("\n");
    }
}

一维dp数组（滚动数组）

上面的dp数组相当于将$dp[i-1]$拷贝到$dp[i]$上面，那么就能只用一个一维数组$dp[j]$。这就是滚动数组，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

1.确定dp数组的定义

在一维dp数组中，$dp[j]$表示：容量为j的背包，所背的物品价值可以最大为$dp[j]$
2.一维dp数组的递推公式

$dp[j]$可以通过$dp[j - weight[i]]$推导出来，表示的意思就是容量为$j-weight[i]$背包所背的最大价值。$dp[j-weight[i]]+value[i]$表示容量为j-物品i重量的背包加上物品i的价值。

此时dp[j]有两个选择，一个是取自己dp[j]相当于二维dp数组中的$dp[i-1][j]$，即不放物品i，一个是取$dp[j - weight[i]] + value[i]$，也就是放物品i。所以递归公式为

$dp[j] = max(dp[j], dp[j - weight[i]] + value[i])$
3.一维dp数组如何初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

对于其他位置的初始化，根据递推公式，dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

4.一维dp数组遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

一维数组遍历的时候，背包是从大到小的，因为倒序遍历是为了保证物品i只被放入一次。

5.整体代码

public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWight = 4;
    testWeightBagProblem(weight, value, bagWight);
}
  
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
    int wLen = weight.length;
    //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
    int[] dp = new int[bagWeight + 1];
    //遍历顺序：先遍历物品，再遍历背包容量
    for (int i = 0; i < wLen; i++){
        for (int j = bagWeight; j >= weight[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    //打印dp数组
    for (int j = 0; j <= bagWeight; j++){
        System.out.print(dp[j] + " ");
    }
}

2 完全背包

有N件物品和一个最多能背重量为W的背包，第i件物品的重量是wight[i]，得到的价值是value[i]，每件物品都有无限个，也就是可以放入背包多次，求解将哪些物品装入背包里面的物品价值总和最大。

完全背包和01背包的唯一不同的在于每件物品有无限件。

所以在更新的时候，01背包是从大到小更新：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

而完全背包可以添加多次，所以从小到大更新：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}