Location>code7788 >text

Dynamic Programming Models - Hitting Home

Popularity：61 ℃/2024-08-20 16:21:01

Ah Fook, the thief (Harry Potter)

You can try this question after reading this article:/problems/house-robber/

img

Analysis of dynamic planning ideas

  • Let the number of stores we robbed beiThe value captured and the value added to thedp , then dp is clearlyiA function of a function of a function of a function of a function of a function of a function of a function of a function of a function, then we usedp[i]as a state variable.dp[i]pre-stealingiMaximum value that can be captured by a home store

State variables and what they mean

  • From the above analysis, we establishdp[i] as a state variable, anddp[i]The implication is that stealing beforeiMaximize the revenue of your store.

recurrence formula

  • We setdp[i] , there are two states at this position of i:
    • 1. The i-th store does not steal -dp[i]=dp[i-1]
    • 2. The ith shoplifting -dp[i]=dp[i-2]+w[i], w[i] is the value of the ith store

The details are shown below:

  • img

Traversal order:

  • From the two-step analysis above, it is clear thatdp[i]The state must be determined by the precedingdp[i-1]，dp[i-2], which is introduced, so that the traversal order must be front-to-back traversal.

How is it initialized?

  • We first have to deal with the boundary conditions:dp[0]cap (a poem)dp[1]What to do with it?
  • The biggest value of stealing from the first 0 stores is obviously the0The maximum value of stealing from the previous 1 store is obviouslyw[1]
  • After dealing with the boundary conditions, we can then recurse from front to back based on the recurrence formula

Example of verifying a dp array

Subscripts: 1, 2, 3, 4

w[i]：10，7，6，14

dp[i]：10，10，16，24

  • The analysis of sample 2 shows that our dp array is not analyzed incorrectly. Thus we verified the correctness of our dp array.

make superior

  • We can usedp[i-1]The state of the direct introduction of thedp[i]The state of the art.

  • Our state representation can be optimized to:

    • f[i][0]denotes the maximum value that can be obtained without stealing from the ith store
    • f[i][1]denotes the maximum value that can be obtained by stealing the ith store

  • Then our state transfer equation can be derived fromdp[i-1]Introducing, not stealing the ith store, then we can either steal the i-1st store or not steal it, and we choose the maximum of the two, and we must only choose not to steal the i-1st store if we steal the ith store.

    • No stealing:dp[i][0]=max(dp[i-1][0],dp[i-1][1])
    • Stealing:dp[i][1]=dp[i-1][0]+w[i]

    img

Optimized boundary treatment:

  • No stealing from the 1st store:f[i][0]=0
  • Stealing the 1st store:f[i][1]=w[1]

Optimized code handling:

scanf("%d",&t)
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        f[1][0]=0;f[1][1]=w[1];
        for(int i=2;i<=n;i++){
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            f[i][1]=f[i-1][0]+w[i];
        }
        printf("%d\n",max(f[n][0],f[n][1]));
    }

Summary:

img

  • The first of the two approaches we described above is called step-by-step transfer, and the second is called categorical transfer, and in some cases, both can be used, while in some topics, only categorical transfer can be used, as we will also describe later! We hope you understand both approaches.
<Previous Next>