Is dynamic programming with combined inner loop and outer loop interchangeable?

Question

I am a bit confused about the dynamic programming solution for the total amount, that you are given a list of numbers and a total amount, and you want to calculate how many ways you can summarize with this target amount. Numbers can be reused several times. I got confused in the inner loop and the outer loop that they are interchangeable or not. Can someone explain the difference between the next two, and in which case we will use one, but not the other, or are they the same.

int [] counts = new int[total];
counts[0] = 1;

// (1) 
for(int i = 0; i <= total; i++) {
   for(int j = 0; j < nums.length; j++) {
       if(i >= nums[j])
          counts[i] += counts[i - nums[j]];
   }
}

// (2)
for(int j = 0; j < nums.length; j++)
   for(int i = nums[j]; i <= total; i++) {
       counts[i] += counts[i - nums[j]];
   }
}

Answer 1

The two versions are really different, which gives different results.

nums = {2, 3} .

1 nums, total. " " , . , 5 2. ( 2) 1 nums[3] ( 3) 1 nums[2]. , 2 3, 2 [2, 3] [3, 2].

2, , nums, total. , , ( ), 1, " " , , . (2) 0 ( 0 ), 1. , 2 , , 1, [2, 3], [3, 2].

, nums , .

Answer 2

, , , .

counts[i] counts[i - nums[j]]; j nums.

    // (1) 
    for(int i = 0; i < total; i++) {
       for(int j = 0; j < nums.length; j++) {
           if(i >= nums[j])
              counts1[i] += counts1[i - nums[j]];
       }
    }

0 total . . nums , .

    // (2)
    for(int j = 0; j < nums.length; j++){
       for(int i = nums[j]; i < total; i++) {
            counts2[i] += counts2[i - nums[j]];
       }
    }

. . , .

? - . :

public class dyn {
    public static void main(String[] args) {

        int total = 50;
        int[] nums = new int[]{1, 5, 10};

        int [] counts1 = new int[total];
        int [] counts2 = new int[total];
        counts1[0] = 1;
        counts2[0] = 1;

        // (1) 
        for(int i = 0; i < total; i++) {
           for(int j = 0; j < nums.length; j++) {
               if(i >= nums[j])
                  counts1[i] += counts1[i - nums[j]];
           }
        }

        // (2)
        for(int j = 0; j < nums.length; j++){
           for(int i = nums[j]; i < total; i++) {
                counts2[i] += counts2[i - nums[j]];
           }
        }

        for(int k = 0; k < total; k++){
            System.out.print(counts1[k] + ",");
        }
        System.out.println("");
        for(int k = 0; k < total; k++){
                System.out.print(counts2[k] + ",");
        }

    }
}

.

, counts[i] . counts[6] , counts[5] counts[1], , , , counts[4], counts[3], counts[2] counts[0]. , ( ) .

:

( ) :

nums.

?

( ). , int[] nums = new int[]{3, 6}, counts[3+6] , count[3] count[6] , , , .

Answer 3

, .

@Amit, nums = {2, 3} .

S (n) = S (n-3) + S (n-2)

, , {x_1, x_2, x_3, ... ,x_k}:

S (n) = S (n-x_1) + S (n-x_2) +... + S (n-x_k)

, S(n) (, ) , 0 total.

S_2 (n) :

S_1 (n) = S_1 (n-2)

S_2 (n) = S_1 (n) + S_2 (n-3)

{x_1, x_2, x_3, ... ,x_k}:

S_1 (n) = S_1 (n-x_1)

S_2 (n) = S_1 (n) + S_2 (n-x_2)

...

S_k (n) = S_ {k-1} (n) + S_k (n-x_k)

; . , .

, :

S_2 (, ) S_2, S_1.

, , 0 nums.

, , counts.

? @Amit, , total, . , , nums = {2, 3}:

list, - , - .

append, , , .

• 2,

• 3,

• 5?

a 3 , 2 .. p >

( 5) = ( 3) + ( 2)

.

• 2 5 (0)

• 2 3 2 (1)

, a 3 .

, " 2" - " 2 3 's". " 2 3 's" " 2", !

, java

3 2.

public static int r(int n){
    if(n < 0)
        return 0;
    if(n == 0)
        return 1;
    return r(n-2) + r(n-3);
}

The following set of recursive functions calculates the values ​​for the second cycle with examples of 3and 2.

public static int r1(int n){
    if(n < 0)
        return 0;
    if(n == 0)
        return 1;
    return r1(n-2);

}

public static int r2(int n){
    if(n < 0){
        return 0;
    }
    return r1(n) + r2(n-3);
}

I checked them before 10and they look right.