算法注意---1、取用数据之前一定要保证数据存在

算法注意---1、取用数据之前一定要保证数据存在

一、总结

一句话总结：

动态规划中，f[j]=f[j] + f[j-w[i]]结构，肯定要保证j-w[i]>=0，也就是取数据之前，一定要保证数据是存在的

1、算法里面常常描述的状态是什么意思？

|||-being

（比如初始状态、中间状态、结束状态）
（又比如枚举条件里面的可预先确定每个状态的元素个数）

|||-end

状态可以看做要求的结果，就像x+y=z里面的z，z==0就是初始状态，z=比如100就是结束状态，那么z==50就是中间状态

2、枚举法的条件（不必深究）？

1、【等式可写：能进行if判断】：可预先确定每个状态的元素个数。如百钱买百鸡，3文钱一只鸡的状态元素可预先确定。

2、【循环可做：能写for】：状态元素之间必须为一个连续的值域，方便一一枚举。

可预先确定每个状态的元素个数。如百钱买百鸡，3文钱一只鸡的状态元素可预先确定。
状态元素之间必须为一个连续的值域，方便一一枚举。如果值域为实数级，每两个值之间有无穷个数，这就不能枚举出所有可能的值。
对于满足以上两个条件的问题，采用穷举法时，可以先确定枚举对象、枚举范围和判定条件，再一一枚举所有可能的解，验证是否是问题的解。

3、枚举法感觉差了点什么？

枚举法要是差了点，就是差的枚举法敲代码技巧：也就是 枚举变量、枚举范围、枚举判断条件

枚举变量：
枚举范围：
枚举判断条件：

4、枚举法做题除了枚举法敲代码技巧，还差一点，就是算法步骤？

算法、算法步骤、算法注意点（这里就是枚举法敲代码技巧）缺一不可，有这三个东西，代码非常好敲，不容易出错

5、动态规划中，f[j]=f[j] + f[j-w[i]]结构，肯定要保证j-w[i]>=0？

也就是取数据之前，一定要保证数据是存在的

6、动态规划填表时，下一行要复制上一行的数据，比如f[i][j]=f[i-1][j] + f[i-1][j-w[i]]中，注意点是什么？

不仅要保证j-w[i]>=0的时候复制数据，还要保证j-w[i]小于0的时候复制数据

//2、做动态规划
for(int i=0;i<=1000;i++) f[i][0]=1;
for(int i=1;i<=num;i++){
    for(int j=1;j<=1000;j++){
        //填表下一行的数据要复制上一行的数据
        if(j-w[i]>=0)
        f[i][j]=f[i-1][j] + f[i-1][j-w[i]];
        else 
        f[i][j]=f[i-1][j];
    }
}

7、序列转换成循环，其中的变化的关键是什么，比如序列1 1 2 3 3 5 10 20转换成循环2(1g) 1(2g) 2(3g) 1 1 1？

准确点来说，就是中间加了一层循环来刷表，也就是增加一个物品刷一次表

dp的转移由f(n-1)=>f(n)【if(j-w[i]) f[j]=f[j-w[i]]】变成了f(n)=>f(n+1)【if(dp[k]) dp[k+b[i]]=1】，因为转成循环的时候，循环的语义变成每增加一个物品怎样怎样
dp的转移并没有改变
for(int i=1;i<=6;i++)
    for(int j=1;j<=a[i];j++)//第i种砝码有a[i]个
        for(int k=mx;k>=0;k--)
            if(dp[k]==true)
                dp[k+b[i]]=true;//标记

8、序列转换成循环，敲代码的一个注意点是什么，比如序列1 1 2 3 3 5 10 20转换成循环2(1g) 1(2g) 2(3g) 1 1 1？

【起始条件和终止条件】：因为减变成了加，所以循环刷表的起始和终止条件就变了，这里一定要注意一下，否则可能因为找不到初始条件而发生填表错误

dp的转移由f(n-1)=>f(n)【if(j-w[i]) f[j]=f[j-w[i]]】变成了f(n)=>f(n+1)【if(dp[k]) dp[k+b[i]]=1】，因为转成循环的时候，循环的语义变成每增加一个物品怎样怎样
准确点来说，就是中间加了一层循环来刷表，也就是增加一个物品刷一次表
//2、做动态规划
f[0] = 1;
for (int i = 1; i <= 6; i++)
{
    for (int k = 1; k <= n[i]; k++)
    {
        //这里要大于等于零，要不然永远跑不到f[0]这里来，初始化的数据就没用了，永远是0 
        for (int j = 1000; j >= 0; j--)
        {
            //填表下一行的数据要复制上一行的数据
            if (f[j])
                f[j + b[i]] = 1;
        }
    }
}

9、动态规划中，中间层循环的真正意义（动态规划状态转移方程中没有用到的变量）？

让表再刷一遍（比如下面实例中背包问题的一维的表）

//2、做动态规划
for (int i = 0; i <= 1000; i++)
    f[i][0] = 1;
for (int i = 1; i <= 6; i++)//遍历六种砝码
{
    for (int k = 1; k <= n[i]; k++)//依次增加砝码的个数
    {
        //其实也就是让下面的表再刷一遍
        for (int j = 1; j <= 1000; j++)
        {
            //填表下一行的数据要复制上一行的数据
            
            if (j - b[i] >= 0)
                f[i][j] = f[i - 1][j] | f[i - 1][j - b[i]];
            else
                f[i][j] = f[i - 1][j];
        }
    }
}

10、用二维表来刷无限背包的易错点？

中间k层循环的意义就是不断的刷表，而我希望的是不断的拿我更新好的这一行来刷这一行，而下面的代码却是总是拿上一行来刷这一行，所以肯定出问题

这就是背包问题里面的无限背包问题

for (int i = 1; i <= 6; i++)//遍历六种砝码
{
    for (int k = 1; k <= n[i]; k++)//依次增加砝码的个数
    {
        //其实也就是让下面的表再刷一遍
        for (int j = 1; j <= 1000; j++)
        {
            //填表下一行的数据要复制上一行的数据
            //出错的原因就是我根本就是希望拿前面的值来耍后面的值
            //而这里总是拿上一行的值来刷的，肯定就有问题
            if (j - b[i] >= 0)
                f[i][j] = f[i - 1][j] || f[i - 1][j - b[i]];
            else
                f[i][j] = f[i - 1][j];
        }
    }
}

二、内容在总结中

博客对应课程的视频位置：